跳转至

2848. 与车相交的点

题目描述

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 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 。

 

提示：

  • 1 <= nums.length <= 100
  • nums[i].length == 2
  • 1 <= starti <= endi <= 100

解法

方法一：差分数组

我们创建一个长度为 $110$ 的差分数组 $d$，然后遍历给定的数组，对于每个区间 $[a, b]$，我们令 $d[a]$ 增加 $1$，$d[b + 1]$ 减少 $1$。最后我们遍历差分数组 $d$，求每个位置的前缀和 $s$，如果 $s > 0$，则说明该位置被覆盖，我们将答案增加 $1$。

时间复杂度 $O(n)$，空间复杂度 $O(M)$。其中 $n$ 是给定数组的长度，而 $M$ 是数组中元素的最大值。

1
2
3
4
5
6
7
class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        d = [0] * 110
        for a, b in nums:
            d[a] += 1
            d[b + 1] -= 1
        return sum(s > 0 for s in accumulate(d))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        int[] d = new int[110];
        for (var e : nums) {
            d[e.get(0)]++;
            d[e.get(1) + 1]--;
        }
        int ans = 0, s = 0;
        for (int x : d) {
            s += x;
            if (s > 0) {
                ans++;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        int d[110]{};
        for (auto& e : nums) {
            d[e[0]]++;
            d[e[1] + 1]--;
        }
        int ans = 0, s = 0;
        for (int x : d) {
            s += x;
            ans += s > 0;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func numberOfPoints(nums [][]int) (ans int) {
    d := [110]int{}
    for _, e := range nums {
        d[e[0]]++
        d[e[1]+1]--
    }
    s := 0
    for _, x := range d {
        s += x
        if s > 0 {
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function numberOfPoints(nums: number[][]): number {
    const d: number[] = Array(110).fill(0);
    for (const [a, b] of nums) {
        d[a]++;
        d[b + 1]--;
    }
    let ans = 0;
    let s = 0;
    for (const x of d) {
        s += x;
        if (s > 0) {
            ans++;
        }
    }
    return ans;
}

评论