力扣（leetcode）每日一题 2848 与车相交的点

2848. 与车相交的点 - 力扣（LeetCode）

题干

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

解法1

public static int numberOfPoints(List<List<Integer>> nums) {TreeMap<Integer, Integer> map = new TreeMap<>();// 先进行排序  如果有线段1，10和1，5 在map中保证存放的是1，10这个数值更大的for (int i = 0; i < nums.size(); i++) {List<Integer> integers = nums.get(i);Integer key = integers.get(0);Integer valueOrigin = integers.get(1);Integer value = map.get(key);if (value == null || value < valueOrigin) {map.put(key, valueOrigin);}}int count = 0;// 再进行遍历Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();int max = 0; // 这里的max是最大结算点while (iterator.hasNext()) {Map.Entry<Integer, Integer> entry = iterator.next();Integer key = entry.getKey();Integer value = entry.getValue();if (key > max) {  // 如果max为3 这里的线段为4，8 直接刷记录然后更新max为8 count += value - key + 1;max = value;}if (key <= max && value > max) { // 这里max为6    线段为4，8   需要更新的点是7到8 因为max已经结算过了，所以这里不需要加1count += value - max;max = value;}}return count;}

在这里插入图片描述

复杂度应该是n * logN + n 这里和数值无关

题解的复杂度是n+c c是元素的范围
下意识觉得元素的范围会很大是10的9次方级别。

解法2

讲一下题解的第二种做法

一个数组上，从左边到右边，如果有线段开始，count就加上1，如果有线段结束，count就减去1
这样count大于1 的位置上就肯定是有线段覆盖的。

 public static int numberOfPoints(List<List<Integer>> nums) {int[] arr = new int[102];for (List<Integer> num : nums) {arr[num.get(0)]++; // 获取count，arr[num.get(1) + 1]--; // 归还count}int count = 0;int res = 0;for (int i : arr) {count += i;if (count > 0) {res++;}}return res;}