class Solution {
public:
int numberOfPoints(vector<vector<int>>& nums) {
}
};
8029. 与车相交的点
给你一个下标从 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 <= 100nums[i].length == 21 <= starti <= endi <= 100原站题解
rust 解法, 执行用时: 2 ms, 内存消耗: 2.1 MB, 提交时间: 2024-09-15 12:33:54
impl Solution {
pub fn number_of_points(nums: Vec<Vec<i32>>) -> i32 {
let max_end = nums.iter().map(|interval| interval[1]).max().unwrap() as usize;
let mut diff = vec![0; max_end + 2]; // 注意下面有 end+1
for interval in nums {
diff[interval[0] as usize] += 1;
diff[(interval[1] + 1) as usize] -= 1;
}
let mut ans = 0;
let mut s = 0;
for d in diff {
s += d;
if s > 0 {
ans += 1;
}
}
ans
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-11 06:19:35
class Solution:
def numberOfPoints(self, nums: List[List[int]]) -> int:
max_end = max(end for _, end in nums)
diff = [0] * (max_end + 2)
for start, end in nums:
diff[start] += 1
diff[end + 1] -= 1
return sum(s > 0 for s in accumulate(diff))
java 解法, 执行用时: 1 ms, 内存消耗: 42.1 MB, 提交时间: 2023-09-11 06:19:08
class Solution {
public int numberOfPoints(List<List<Integer>> nums) {
var diff = new int[102];
for (var p : nums) {
diff[p.get(0)]++;
diff[p.get(1) + 1]--;
}
int ans = 0, s = 0;
for (int d : diff) {
s += d;
if (s > 0) {
ans++;
}
}
return ans;
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 4 MB, 提交时间: 2023-09-11 06:18:51
func numberOfPoints(nums [][]int) (ans int) {
diff := [102]int{}
for _, p := range nums {
diff[p[0]]++
diff[p[1]+1]--
}
s := 0
for _, d := range diff {
s += d
if s > 0 {
ans++
}
}
return
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 23.8 MB, 提交时间: 2023-09-11 06:18:36
class Solution {
public:
int numberOfPoints(vector<vector<int>> &nums) {
int diff[102]{};
for (auto &p: nums) {
diff[p[0]]++;
diff[p[1] + 1]--;
}
int ans = 0, s = 0;
for (int d: diff) {
s += d;
ans += s > 0;
}
return ans;
}
};
javascript 解法, 执行用时: 76 ms, 内存消耗: 43.4 MB, 提交时间: 2023-09-11 06:18:21
/**
* @param {number[][]} nums
* @return {number}
*/
var numberOfPoints = function(nums) {
const diff = new Array(102).fill(0);
for (const p of nums) {
diff[p[0]]++;
diff[p[1] + 1]--;
}
let ans = 0, s = 0;
for (const d of diff) {
s += d;
ans += s > 0;
}
return ans;
};