工程技术研究中心网站建设要求,购物建设网站,哈尔滨市建工建设有限公司,做网站的岗位好吗2848. 与车的相交点
today 2848. 与车的相交点
题目描述
给你一个下标从 0开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i #xff0c;nums[i] [starti, endi] #xff0c;其中 s t a r t i start_i starti 是第 i 辆车的起点#xff0c; e 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[endi1] true。
最后遍历arr统计true的个数即可。
复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。
代码实现
C版本
class Solution {
public:int numberOfPoints(vectorvectorint nums) {int nnums.size();int ans0;vectorbool arr(101,0);for(int i0;in;i){for(int jnums[i][0];jnums[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];jnums[i][1];j{if(!arr[j]){ansarr[j]true}}}return ans
}Python版本
class Solution(object):def numberOfPoints(self, nums):n[False]*101llen(nums)ans0for i in range(0,l):for j in range(nums[i][0],nums[i][1]1):if not n[j] :ans1n[j]Truereturn ans
