Easy

题目描述

给你一个下标从 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

解题思路

这道题要求统计数轴上被汽车覆盖的整数点数量。根据数据范围较小（坐标最大为100），我们可以采用多种方法：

方法1：哈希集合（推荐）

遍历每辆汽车的区间，将区间内的所有整数点添加到集合中。由于集合会自动去重，最终集合的大小就是答案。这种方法简单直观，时间复杂度合理。

方法2：差分数组

使用差分数组标记每个区间的开始和结束，然后通过前缀和计算每个点被覆盖的情况。

方法3：区间合并

先对区间按起点排序，然后合并重叠区间，最后统计合并后区间的总长度。

由于数据范围小且要求简洁，推荐使用哈希集合方法，代码简单且易于理解。

代码实现

class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        unordered_set<int> points;
        
        for (auto& car : nums) {
            for (int i = car[0]; i <= car[1]; i++) {
                points.insert(i);
            }
        }
        
        return points.size();
    }
};

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        points = set()
        
        for start, end in nums:
            for i in range(start, end + 1):
                points.add(i)
        
        return len(points)

public class Solution {
    public int NumberOfPoints(IList<IList<int>> nums) {
        HashSet<int> points = new HashSet<int>();
        
        foreach (var car in nums) {
            for (int i = car[0]; i <= car[1]; i++) {
                points.Add(i);
            }
        }
        
        return points.Count;
    }
}

var numberOfPoints = function(nums) {
    const points = new Set();
    
    for (const [start, end] of nums) {
        for (let i = start; i <= end; i++) {
            points.add(i);
        }
    }
    
    return points.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
哈希集合O(n × L)O(P)
差分数组O(n + maxVal)O(maxVal)
区间合并O(n log n)O(1)

其中 n 是汽车数量，L 是平均区间长度，P 是被覆盖的点数，maxVal 是坐标最大值（100）。

相关题目