【LeetCode】区间（合并、插入、重叠区间、最小区间······）

落日映苍穹つ 2023-01-06 15:52 182阅读 0赞

### 文章目录 ###

*   *   *  汇总区间★
         *  无重叠区间★★
         *  合并区间★★
         *  插入区间★★★
         *  最小区间★★★
         *  区间和的个数★★★

--------------------

### 汇总区间★ ###

[LeetCode228. 汇总区间][LeetCode228.]

【**题目**】给定一个无重复元素的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 \[a,b\] 应该按如下格式输出：

*  “a->b” ，如果 a != b
 *  “a” ，如果 a == b

【**示例**】

输入：nums = [0,2,3,4,6,8,9]
    输出：["0","2->4","6","8->9"]
    解释：区间范围是：
    [0,0] --> "0"
    [2,4] --> "2->4"
    [6,6] --> "6"
    [8,9] --> "8->9"

【**解题思路**】

*  无连续的数字单独作为区间
 *  有连续数字取区间两端

class Solution {
        
        public List<String> summaryRanges(int[] nums) {
        
            List<String> list = new ArrayList<>();
            for(int i = 0; i < nums.length; i++) {
        
                StringBuffer sb = new StringBuffer();
                sb.append(nums[i]);
                if(i + 1 < nums.length && nums[i + 1] - nums[i] == 1) {
        
                    int j = i + 1;
                    while(j + 1 < nums.length && nums[j + 1] - nums[j] == 1) {
        
                        j++;
                    }
                    i = j;
                    sb.append("->");
                    sb.append(nums[j]);
                }
                list.add(sb.toString());
            }
            return list;
        }
    }

--------------------

### 无重叠区间★★ ###

[LeetCode435. 无重叠区间][LeetCode435.]

【**题目**】给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

*  可以认为区间的终点总是大于它的起点。
 *  区间 \[1,2\] 和 \[2,3\] 的边界相互“接触”，但没有相互重叠。

【**示例**】

输入: [ [1,2], [2,3], [3,4], [1,3] ]
    输出: 1
    解释: 移除 [1,3] 后，剩下的区间没有重叠。

【**解题思路**】贪心法

**方法一**：按左端点排序

class Solution {
        
        public int eraseOverlapIntervals(int[][] intervals) {
        
            if(intervals == null || intervals.length == 0) return 0;
            Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));
            int count = 0;    //记录移除区间个数
            int end = intervals[0][1];   //记录区间右端
            for(int i = 1; i < intervals.length; i++) {
        
                if(intervals[i][0] < end) {
        
                    count++;
                    //取右端比较小的，这样才能容纳更多的区间
                    end = Math.min(end, intervals[i][1]);
                }else {
        
                    end = intervals[i][1];
                }
            }
            return count;
        }
    }

**方法二**：按右端点排序

class Solution {
        
        public int eraseOverlapIntervals(int[][] intervals) {
        
            if(intervals == null || intervals.length == 0) return 0;
            Arrays.sort(intervals, (o1, o2) -> (o1[1] - o2[1]));
            int count = 0;    //记录移除区间数
            int end = intervals[0][1];  //记录区间最右端
            for(int i = 1; i < intervals.length; i++) {
        
                if(intervals[i][0] < end) {
        
                    count++;
                }else {
        
                    end = intervals[i][1];
                }
            }
            return count;
        }
    }

--------------------

### 合并区间★★ ###

[LeetCode 56. 合并区间][LeetCode 56.]

【**题目**】给出一个区间的集合，请合并所有重叠的区间。

【**示例**】

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

【**解题思路**】

**方法一**：自定义排序

先按照左端点排序，之后顺序遍历，若左右元素相交，则更新区间大小，否则加入区间结果集

class Solution {
        
        public int[][] merge(int[][] intervals) {
        
            if(intervals == null || intervals.length == 0) return new int[][]{
        {
        }};
            Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
            List<int[]> list = new ArrayList<int[]>();
            int le = intervals[0][0], ri = intervals[0][1];
            for(int i = 1; i < intervals.length; i++) {
        
                if(intervals[i][0] > ri) {
        
                    list.add(new int[]{
        le, ri});
                    le = intervals[i][0];
                    ri = intervals[i][1];
                }else {
        
                    ri = Math.max(ri, intervals[i][1]);
                }
            }
            list.add(new int[]{
        le, ri});
            return list.toArray(new int[list.size()][2]);
        }
    }

**方法二**：位图

使用`BitSet`模拟坐标轴

class Solution {
        
        public int[][] merge(int[][] intervals) {
        
            BitSet bitSet = new BitSet();
            int max = 0;
            for(int[] e : intervals) {
        
                int t = e[1] * 2 + 1;    //乘以2是为了标记类似[a, a]的区间
                bitSet.set(e[0] * 2 , t, true);
                max = Math.max(max, t);
            }
            List<int[]> list = new ArrayList<int[]>();
            int index = 0;
            while(index < max) {
        
                int start = bitSet.nextSetBit(index);
                int end = bitSet.nextClearBit(start);
                list.add(new int[]{
        start / 2, (end - 1) / 2});
                index = end;
            }
            return list.toArray(new int[list.size()][]);
        }
    }

--------------------

### 插入区间★★★ ###

[LeetCode 57. 插入区间][LeetCode 57.]

【**题目**】给出一个\*无重叠的 ，\*按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

【**示例**】

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
    输出：[[1,2],[3,10],[12,16]]
    解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠

【**解题思路**】

分三步走：

*  小于插入区间左端点的不用合并
 *  合并区间时，左端点取最小值，右端点取最大值
 *  大于插入区间右端点的不用合并

class Solution {
        
        public int[][] insert(int[][] intervals, int[] newInterval) {
        
            int t = 0;
            List<int[]> list = new ArrayList<int[]>();
            
            //小于newInterval[0](左端点)的不用合并
            while(t < intervals.length && intervals[t][1] < newInterval[0]){
        
                list.add(intervals[t]);
                ++t;
            }
            
            //合并区间    左端点取最小，右端点取最大
            while(t < intervals.length && intervals[t][0] <= newInterval[1]){
        
                newInterval[0] = Math.min(newInterval[0], intervals[t][0]);
                newInterval[1] = Math.max(newInterval[1], intervals[t][1]);
                ++t;
            }
            list.add(newInterval);
            
            //大于newInterval[1](右端点)的不用合并
            while(t < intervals.length){
        
                list.add(intervals[t]);
                ++t;
            }
            return list.toArray(new int[0][]);
        }
    }

--------------------

### 最小区间★★★ ###

[LeetCode 632. 最小区间][LeetCode 632.]

【**题目**】你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 `b-a < d-c` 或者在 `b-a == d-c` 时 `a < c`，则区间 `[a,b]` 比 `[c,d]` 小。

**提示**：

*  `nums.length == k`
 *  `1 <= k <= 3500`
 *  `1 <= nums[i].length <= 50`
 *  `-105 <= nums[i][j] <= 105`
 *  `nums[i]` 按非递减顺序排列

【**示例**】

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
    输出：[20,24]
    解释： 
    列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
    列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
    列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

【**解题思路**】

滑动窗口

将每个列表中的数字与其列表位置映射为二维数组，并按大小排序，

接着若滑动窗口中包含每个分组中的数，就可以更新结果了

class Solution {
        
        public int[] smallestRange(List<List<Integer>> nums) {
        
            int N = 0;
            for(List<Integer> num : nums) N += num.size();
    
            //将列表映射为一个二维数组{值， 分组}
            int[][] help = new int[N][2];
            int k = 0;
            for(int i = 0; i < nums.size(); i++) {
        
                List<Integer> num = nums.get(i);
                for(int j = 0; j < num.size(); j++) {
        
                    help[k][0] = num.get(j);
                    help[k][1] = i;
                    k++;
                }
            }
    
            Arrays.sort(help, (o1, o2) -> o1[0] - o2[0]);
            
            int[] res = {
        0, 0};
            int[] group = new int[nums.size()];
            int count = 0;
            k = 0;
            for(int i = 0; i < N; i++) {
        
                //记录滑动窗口内组数
                if(0 == group[help[i][1]]++) count++;
                if(count == group.length) {
        
                    //收缩窗口
                    while(group[help[k][1]] > 1) group[help[k++][1]]--;
                    //更新结果
                    if(res[0] == 0 && res[1] == 0 || help[i][0] - help[k][0] < res[1] - res[0]) {
        
                        res[0] = help[k][0];
                        res[1] = help[i][0];
                    }
                }
            }
    
            return res;
    
        }
    }

--------------------

### 区间和的个数★★★ ###

[LeetCode 327. 区间和的个数][LeetCode 327.]

【**题目**】给定一个整数数组 `nums`，返回区间和在 `[lower, upper]` 之间的个数，包含 `lower` 和 `upper`。  
区间和 `S(i, j)` 表示在 `nums` 中，位置从 `i` 到 `j` 的元素之和，包含 `i` 和 `j (i ≤ j)`。

**说明:**  
最直观的算法复杂度是 `O(n^2)` ，请在此基础上优化你的算法。

【**示例**】

输入: nums = [-2,5,-1], lower = -2, upper = 2,
    输出: 3 
    解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

【**解题思路**】

**方法一**：暴力法

class Solution {
        
        public int countRangeSum(int[] nums, int lower, int upper) {
        
            int count = 0;
            for(int i = 0; i < nums.length; i++){
        
                long sum = 0;
                for(int j = i; j < nums.length; j++){
        
                    sum += nums[j];
                    if(sum >= lower && sum <= upper){
        
                        count++;
                    }
                }
            }
            return count;
        }
    }

**方法二**：归并排序思想

解题方法来自官方题解  
*https://leetcode-cn.com/problems/count-of-range-sum/solution/qu-jian-he-de-ge-shu-by-leetcode-solution/*

具体思路如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

class Solution {
        
        //归并复制辅助数组
        private static long[] aux;
        
        public int countRangeSum(int[] nums, int lower, int upper) {
        
            if(nums == null || nums.length == 0) return 0;
            aux = new long[nums.length + 1];
    
            //前缀和数组
            long[] pre = new long[nums.length + 1];
            for(int i = 0; i < nums.length; i++) {
        
                pre[i + 1] = pre[i] + nums[i];
            }
    
            return sort(pre, 0, pre.length - 1, lower, upper);
        }
    
        private int sort(long[] pre, int le, int ri, int lower, int upper) {
        
            if(le >= ri) return 0;
            int mid = le + (ri - le) / 2;
            int countleft  = sort(pre, le, mid, lower, upper);
            int countright = sort(pre, mid + 1, ri, lower, upper);
            int countcur = merge(pre, le, mid, ri, lower, upper);
            return countleft + countright + countcur;
        }
    
        private int merge(long[] pre, int le, int mid, int ri, int lower, int upper) {
        
            //复制
            for(int k = le; k <= ri; k++) {
        
                aux[k] = pre[k];
            }
    
            //计算符合要求的区间和个数
            int count = 0;
            int k = le, i = mid + 1, j = mid + 1;
            while(k <= mid) {
        
                while(i <= ri && pre[i] - pre[k] < lower)  i++;
                while(j <= ri && pre[j] - pre[k] <= upper) j++;
                count += j - i;
                k++;
            }
    
            //合并
            k = le;
            i = le;
            j = mid + 1;
            while(i <= mid || j <= ri) {
        
                if(i > mid) {
        
                    pre[k++] = aux[j++];
                }else if(j > ri) {
        
                    pre[k++] = aux[i++];
                }else if(aux[i] <= aux[j]){
        
                    pre[k++] = aux[i++];
                }else {
        
                    pre[k++] = aux[j++];
                }
            }
    
            return count;
        }
    }

[LeetCode228.]: https://leetcode-cn.com/problems/summary-ranges/
[LeetCode435.]: https://leetcode-cn.com/problems/non-overlapping-intervals/
[LeetCode 56.]: https://leetcode-cn.com/problems/merge-intervals/
[LeetCode 57.]: https://leetcode-cn.com/problems/insert-interval/
[LeetCode 632.]: https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/
[LeetCode 327.]: https://leetcode-cn.com/problems/count-of-range-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/85101899c20340b480c5dd80dd8fcdb0.png