Leetcode 分类刷题 —— 排序类（Sort）

1、题目

Leetcode 56. Merge Intervals 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

2、思路

按照区间的左端点排序,在排完序的列表中,判断区间是否重叠,如果重叠就合并,不重叠就添加到结果集。
时间复杂度：排序的时间复杂度是O(nlogn)，其中n是区间的个数。遍历的时间复杂度是O(n)，

3、代码

 class Solution {
    public int[][] merge(int[][] intervals) {
        int m = intervals.length;
        //先按左边界排序
        sorted(intervals,0,m-1);
        //然后逐步合并
        int j=0;  //j指向要与i做对比的最后一个区间的位置
        for(int i=1;i<m;i++) { //i依次向后取
            if(intervals[j][1]>=intervals[i][0]) { //两个区间有交叉
                intervals[j][1]=Math.max(intervals[i][1],intervals[j][1]);
            } else { //两个区间没有交叉，把i位置的向前挪，填补前面数组的空白
                j++;
                intervals[j]=intervals[i];
            }
        }
        return Arrays.copyOf(intervals,j+1);
    }
    private void sorted(int[][] intervals,int left,int right) {
        //快速排序
        if (left>=right) {
            return;
        }
        int[] x = intervals[right];
        int index = left;
        for(int i=left;i<right;i++) {
            if(intervals[i][0]<x[0]) {
                int[] temp = intervals[index];
                intervals[index] = intervals[i];
                intervals[i] = temp;
                index++;
            }
        }
        intervals[right] = intervals[index];
        intervals[index] = x;
        sorted(intervals,left,index-1);
        sorted(intervals,index+1,right);
    }
}

首先，对输入的区间按照起始值进行升序排序，这样可以保证相邻的区间有可能重叠。
然后，创建一个新的列表，用来存放合并后的区间。
遍历排序后的区间，对于每个区间，判断它是否与列表中最后一个区间重叠。
如果不重叠，说明它是一个新的区间，直接添加到列表中。
如果重叠，说明它可以与列表中最后一个区间合并，更新列表中最后一个区间的终止值为两个区间的最大终止值。
最后，将列表转换为二维数组并返回。

class Solution {
    public int[][] merge(int[][] intervals) {
        // Sort the intervals by their start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // Create a list to store the merged intervals
        List<int[]> merged = new ArrayList<>();

        // Iterate over the intervals
        for (int[] interval : intervals) {
            // If the list of merged intervals is empty or if the current interval does not overlap with the previous interval, simply append it
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // Otherwise, there is overlap, so we merge the current and previous intervals
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }

        // Convert the list to an array and return it
        return merged.toArray(new int[merged.size()][]);
    }
}

4、java.util.Arrays#sort

• Arrays.sort()是一个静态方法，用于对数组进行排序，可以对基本类型或对象类型的数组进行排序。
• Arrays.sort()的排序原理取决于数组的类型和大小。
• 对于基本类型的数组，Arrays.sort()使用了双轴快速排序算法，它是快速排序的一种改进，可以更好地处理重复元素和不平衡的分割。
• 对于对象类型的数组，Arrays.sort()使用了归并排序算法，它是一种稳定的排序算法，可以保持相等元素的相对顺序。
• 当对象类型的数组较小（长度小于47）时，Arrays.sort()使用了插入排序算法，它是一种简单而高效的排序算法，适合小规模的数据。

参考文章：
https://leetcode.cn/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode-solution/
Java的Arrays.sort()方法到底用的什么排序算法
类似的区间题目：重叠区间、合并区间、插入区间