2848. 与车相交的点 Easy

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [start_i, end_i] ，其中 start_i 是第 i 辆车的起点，end_i 是第 i 辆车的终点。

返回数轴上被车 任意部分 覆盖的整数点的数目。

示例 1:
输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。

示例 2:
输入：nums = [[1,3],[5,8]]
输出：7
解释：1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交，因此答案为 7 。

解题思路

输入：一个二维整数数组 nums，每个值都代表第 i 个车的停车岂止坐标

输出：返回被车覆盖的整数点的数目

本题属于一维差分问题。

我们首先要知道总共的坐标范围是 [1, 100]

所以这个问题就是在问在 0-100 之内有哪些区域被车覆盖了

我们可以定义一个差分数组 diff = [0] * 102，这里 102是为了预留 end + 1 为 0

然后我们遍历每辆车的覆盖区间并记录每个区间的开始 +1，结束 -1

我们可以得到这样一个差分数组 [...1,0,0,0,-1,...1,0,0,-1...]

然后遍历这个差分数组，当发现这个点 > 0 则说明这个区间开始有车覆盖了，当下次遇到 < 0 的时候说明这个覆盖区间结束了

然后判断区域是否被覆盖 cover += diff[i], cover > 0 则说明被覆盖

覆盖则count += 1，没有则不增加 count

最后返回 count

代码实现

python

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        # 数轴最大只到 100，差分数组范围设为 0~101，预留 end+1
        diff = [0] * 102

        # 遍历每辆车的覆盖区间，使用差分打标记
        for start, end in nums:
            diff[start] += 1       # 区间起点 +1，表示从这里开始被覆盖
            diff[end + 1] -= 1     # 区间终点+1 处 -1，表示从这里开始不再被覆盖

        # 遍历差分数组做前缀和，还原每个位置被覆盖的次数
        count = 0     # 统计被至少覆盖一次的点数
        coverage = 0  # 当前点的累计覆盖次数

        for i in range(102):
            coverage += diff[i]   # 前缀和恢复当前点的覆盖值
            if coverage > 0:
                count += 1        # 被至少一辆车覆盖的点，计入总数

        return count

javascript

/**
 * @param {number[][]} nums
 * @return {number}
 */
var numberOfPoints = function(nums) {
    const diff = Array(102).fill(0);

    for (let [start, end] of nums) {
        diff[start] += 1;
        diff[end + 1] -= 1;
    }

    let cover = 0;
    let count = 0;
    for (let i = 0; i < 102; i++) {
        cover += diff[i];
        if (cover > 0) {
            count ++;
        }
    }

    return count;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

2848 国际版

2848 中文版