LeetCode:2848. 与车的相交点 一次遍历，时间复杂度O(n)
2848. 与车的相交点
today 2848. 与车的相交点
题目描述
给你一个下标从 0开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i ，nums[i] = [starti, endi] ，其中 s t a r t i start_i starti 是第 i 辆车的起点， e n d i end_i endi 是第 i 辆车的终点。
返回数轴上被车任意部分覆盖的整数点的数目。
示例 1：
输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。
示例 2：
示例2：
输入：nums = [[1,3],[5,8]]
输出：7
解释：1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交，因此答案为 7 。
提示：
1 <= nums.length <= 100nums[i].length == 21 <= starti <= endi <= 100
题目解析
题目要求找出任意部分覆盖的整数点的数目。那么我们可以维护一个数组arr，表示所有整数点，由于1 <= starti <= endi <= 100，我们数组的长度为101，其中arr[i]表示整数点i是否被车覆盖。
遍历nums，对于每辆车，我们将 s t a r t i start_i starti 到 e n d i end_i endi 之间的整数点都标记为true，即arr[starti] = true和arr[endi+1] = true。
最后遍历arr，统计true的个数即可。
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)。
- 空间复杂度： O ( 1 ) O(1) O(1)。
代码实现
C++版本：
class Solution {
public:int numberOfPoints(vector<vector<int>>& nums) {int n=nums.size();int ans=0;vector<bool> arr(101,0);for(int i=0;i<n;i++){for(int j=nums[i][0];j<=nums[i][1];j++){if(!arr[j]){ans++;arr[j]=true;}}}return ans;}
};
Go版本：
func numberOfPoints(nums [][]int) int { arr:=make([]bool,101)ans:=0for i:=range(nums){for j:=nums[i][0];j<=nums[i][1];j++{if(!arr[j]){ans++arr[j]=true}}}return ans
}
Python版本：
class Solution(object):def numberOfPoints(self, nums):n=[False]*101l=len(nums)ans=0for i in range(0,l):for j in range(nums[i][0],nums[i][1]+1):if not n[j] :ans+=1n[j]=Truereturn ans