0%

LeetCode Sort

Posted on Edited on In
Symbols count in article: 15k

所谓爱一个人，不是宽裕了想要给予，而是恳切地必须给予。
所谓爱一个人，不是喜欢对方的体温，而是要跟对方的体温越来越接近。所谓爱一个人，是即便对方一直折磨你，你想要的一直讨厌对方，但怎么也讨厌不起来。所谓爱一个人，真的是一件难事。所谓爱，不是不讨厌，而是绝对不能讨厌的意思。
——《请回答1988》

由浅入深介绍和分析各种排序算法，重点给出快排和归并排序的实现思路。

国内面试中经常会问到排序方面问题。如果开放性强的话，可能直接问你有关排序，可以畅所欲言。但是考察得更多的应该还是排序的的思路和代码，尤其是快排、归并。

首先，排序分为比较类排序和非比较类排序，如下图所示：

1O9RkF.png

如何理解比较类排序和非比较类排序？

  1. 比较类排序： 通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn), 因此也称为非线性时间比较类排序。
  • 在高级语言里，大家直接调用系统的排序函数的时候，你可以传入一个参数：comparator(java语言，其他语言可能叫做cmp之类的函数)。也就是说，它比较的对象不一定必须是实数或者int之类的类型，可以是任何结构体或者类的对象。你只需要给它传入一个可以比较两个object之间的前后关系的类型，都可以通过排序算法得到。

像这种通过比较来决定元素间的相对次序，数学上已经证明，时间复杂度不会超过O(logn)，而我们经常用到的，都是这种比较类排序。

  1. 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也成为线性时间非比较类排序。
  • 一般对于整型元素来做的，也就是说可以用线性时间来完成。它可以突破基于比较排序的时间下界，以线性时间完成。

但是非比较类排序的缺点是：一般只能用于整型相关的数据类型。也就是说对于一些比如字符串的排序，或者对象之间的排序，非比较类排序是无能为力的。而且非比较类排序一般需要辅助的内存空间。

非比较类排序基本都是把结果放入到数组中，统计不同元素出现的次数来排序。

常用的排序算法的复杂度分析和稳定性，如下表：

1jSh4g.png

从重要程度来说，更重要的是比较类排序，因为它是泛型的，也是工业编程中用得最多的。

初级排序：O(n^2)

  1. 选择排序(Selection Sort)

每次选择最小值，然后放到待排序数组的起始位置。

  1. 插入排序(Insertion Sort)

从前到后逐步构建有序序列;对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  1. 冒泡排序(Bubble Sort)

嵌套循环，每次查看相邻的元素，如果逆序，则交换。

这三种初级排序没有太大差别，其实是异曲同工的原理。

而面试中，考察技术能力的时候，他考察的一般也都是O(nlogn)的排序，所以准备过程中也应该尽量多花时间去看时间复杂度为O(nlogn)的排序算法。主要是三个：堆排序、快速排序、归并排序。

高级排序 —— O(N*logN)

快速排序(Quick Sort)

数组取标杆pivot，将比pivot小的元素放到pivot左边，比它大的元素放在它的右边，然后依次对左边和右边的子数组继续快排；以达到整个序列有序。

快排用到了分治的思想，首先，如果想要把排序的时间复杂度从O(n^2)降到O(N logN)，那么分治毫无疑问是要考虑的问题。

快排的方法：拿到一个pivot的位置，将所有小于pivot的元素移动到左边去，大于pivot的移动到右边去，且分别对左右侧再进行递归，调用快排。可以通过主定理，证明整个递归下来的时间复杂度为O(N logN)。

快排的样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void quickSort(int[] array, int begin, int end) {
    if (end <= begin) return;
    int pivot = partition(array, begin, end);
    quickSort(array, begin, pivot - 1);
    quickSort(array, pivot + 1, end);
}

static int partition(int[] a, int begin, int end) {
    // pivot: 标杆位置，counter: 小于a[pivot]的元素的个数
    int pivot = end, counter = begin;
    for (int i = begin; i < end; i++) {
        if (a[i] < a[pivot]) {
            int temp = a[counter]; a[counter] = a[i]; a[i] = temp;
            counter++;
        }
    }
    int temp = a[pivot]; a[pivot] = a[counter]; a[counter] = temp;
    return counter;
}

稍微复杂的过程是partition，它做的是，返回一个下标pivot，且能够保证pivot之前的元素都小于pivot，pivot之后的元素都大于pivot。(但是需要注意，每次partition只能保证pivot前面的是小于它的，后面是大于它的，前面和后面不能保证是有序的)

这段代码其实是非常考验基本功的。

实现过程中，我们可以申请一个新的数组，通过比较，把小的元素放到数组的左边，大的元素放到数组的右边。但是如果不能申请一个新的数组，那么这段代码是非常巧妙的。

1
2
3
4
5
6
for (int i = begin; i < end; i++) {
    if (a[i] < a[pivot]) {
        int temp = a[counter]; a[counter] = a[i]; a[i] = temp;
        counter++;
    }
}

一开始把pivot定义在传入的数组的最后的位置，然后根据情况改变pivot的位置。counter用于统计小于a[pivot]的元素的个数。这里的关键是，只要a[i] < a[pivot]，说明a[counter]要和a[i]交换位置。

这里一开始我也没能理解，但是用纸笔模拟了一下之后，发现真的很巧妙。一开始counter和i都是begin，是从相同的地方开始的，然后counter用于指在最后一个小于a[pivot]的元素上，i的值来进行循环，如果碰到比末尾的pivot值大的值，就跳过（因为这个是要留给counter进行交换的,counter此时的作用是把大的元素和后面的i位置的，而且比a[pivot]小元素进行交换），i只要碰到了小于a[pivot]的，就让前面的counter和这个小于a[pivot]的元素交换，从而让大的元素移到后面去，然后把counter往后移，如果此时a[counter]的元素是大于a[pivot]的，那么此时counter所指的元素是为了进行下次交换的。保证counter前面的所有值都是小于a[pivot]的。

一直这样下去，直到begin和end都遍历完了，然后交换a[pivot]和a[counter]，由此一来，绝对可以保证a[piovot]成为一个分水岭，pivot成为一个标杆，a[pivot]左边所有的元素都会是小于a[pivot]的，右边都是大于a[pivot]的。

快排就是这样，大家写的时候，就是把这一段记好，多写几次，多写几次，记住关键的pivot和counter以及它们的作用。

但是需要注意快排的缺陷：如果一个数组本身已经排好序了，那么每一轮排序的时候都会以最后一个数字作为比较的标准，此时快排的效率退化成了O(n^2)。所以，在面试中只要碰到了和排序有关的问题，一定要问清楚具体环境，有哪些条件约束，在得到足够多的信息之后再选择最合适的排序算法。

归并排序(Merge Sort)

归并排序也用到了分治的思想。

归并具体流程：

  1. 把待排序的数组从中间一分为二，注意这个分只是从中间直接”劈开”，不用做任何交换元素的操作。
  2. 对这两个子序列先分别调用归并排序，这样可以保证左边的子序列和右边的子序列在自己的片段区间中是有序的。
  3. 将两个排好序的子序列合并。

归并和快排刚好相反，可以把归并排序看做是快排的逆向操作。为什么？

具体做法不同。归并：先把数组一分为二，在左边和右边都分别调用了排序方法排好序之后，再把左右排好序的两个子数组合并成一个。

快排：先用partition排好序从而找到pivot的位置，然后再用pivot进行大小的”分隔”，和归并排序是完全相反的操作。

然后看代码，首先是mergeSort的主函数部分：

1
2
3
4
5
6
7
8
public static void mergeSort(int[] array, int left, int right) {
    if (right <= left) return;
    int mid = (left + right) >> 1; // (left + right) / 2

    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);
    merge(array, left, mid, right);
}

首先直接从中间一分为二地”劈开”, 得到mid，然后递归，每次都切分一次。最后在每次递归的终止的地方将切分并且排好序的两部分合并。

然后对于merge的逻辑怎么写，之前写过的，把两个有序的链表怎么合并，那里已经知道用O(n)就可以解决。

在这里的情况是，给你一个数组，它的两半部分全部都是排好序的，你怎么把它合并起来？你也可以想象，给你两个数组，这两个数组都是排好序的，怎么把它合并起来。

这种程序题目，逻辑相对来说比较简单，但是对于基础编码功底要求很高。

经过挑选出来的合并的代码，应该是最精简，最漂亮的代码。

如果之前没写过这段代码，多多少少是要花一些功夫的。

应当把这种，把两个有序的数组合并在一起（或者在这里称之为归并），的方法，当成一个代码的模板，记在脑子里。最好能够灵活运用。这是提高你最基础的内容的很重要的一个部分。

merge方法部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 中间数组
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid)   temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
        // 也可以用 System.arraycopy(a, start1, b, start2, length)
    }

这段代码具体在做什么呢？

首先，从left到mid和从mid到right都已经有序了。把这两个子序列合并在一起。

你可以想象为，有两个数组，第一个数组从left到mid，第二个数组是从mid到right。这两个数组分别是有序的，怎样合并起来。

首先，要申请一段额外的内存空间（归并排序必须要申请一块额外的内存空间出来）

int[] temp = new int[right - left + 1]; // 中间数组

需要的大小也没什么好说的，很多申请数组的大小都是要有这么一个+1的内容。

接下来，定义了两个下标i和j, i就是left，j是mid+1，也就是，i表示第一个数组的起始位置，j表示第二个数组的起始位置。k指的是temp这个数组里面已经填入的元素的个数。

关于合并：在看了这段之后，一定要养成一个习惯：要合并两个有序的数组，它永远是这种三段式写法：

1
2
3
4
5
6
while (i <= mid && j <= right) {
    temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}

while (i <= mid)   temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];

具体分析：

第一个while：保证i没有循环完且j也没有循环完（所以有i<=mid和j<=right），然后比较a[i]和a[j]中的较小者，把较小者拿出来放到temp[k]里面去。同时，用了a[i]，就让i++（因为要再去用下一个元素了），用了a[j]，就让j++（同理），然后放入到temp[k]之后，毫无疑问k也要k++。

上面的这一大段逻辑，就三行写完，很是巧妙：

1
2
3
while (i <= mid && j <= right) {
    temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}

但是，强调，这句话不是奇技淫巧！对于编程写得比较多的人，这句话是经常用的！

所以要习惯于写这么一句话。这句话的逻辑是非常清晰的，而且简明扼要。它做得事情就是，比较a[i]和a[j]中的较小者，取出来之后，把较小者赋值给temp[k]，同时a[i]或者a[j]谁被用到，就让下标加一用于下次使用，然后k也要移动用于下一次使用。

这个循环写完之后，可以保证一点，就是i全部走完子数组，或者j全部走完了子数组。

接下来要做的，如果i没有走完，那么把i的剩余部分赋值到temp[k]里面去，或者j没有走完的话，把j剩余部分复制到temp[k]里面去。

1
2
while (i <= mid)   temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];

在这两个while循环也写完之后，你可以发现，整个数组已经完成了归并，放到了temp[]里面了。

因为我们在merge这个函数里面是要对arr[]进行排序，所以我们要再把temp里面的所有元素再拷贝回array里面去。

1
2
3
4
for (int p = 0; p < temp.length; p++) {
    arr[left + p] = temp[p];
}
// 也可以用 System.arraycopy(a, start1, b, start2, length)

对于归并排序的代码，希望大家多多练习，把这段代码写得更细腻。

以及，把这段很能体现编程内力的代码可以在白板上写出来，面试官肯定会刮目相看的。

给出一个时间复杂度为O(n)的排序算法？

理论上是不太合理的，但是如果这么问，那么我们一定要多问问题，问清楚O(n)排序算法的环境和背景。比如要给一个公司的几万名员工按照年龄进行排序，那么，首先，年龄的范围可以定位18-99，这是个有限大小的范围，我们可以申请这么大的数组(但是空间复杂度为O(1)，因为是确定的。)然后遍历一遍所有员工，每次在年龄对应的下标上加1，即可完成按照年龄的排序了。

为什么要考虑排序算法是否稳定？

实际上，如果只是考虑简单地对数字进行排序，那么稳定性是毫无意义的。一个例子是在促销活动中，经过降价的产品应该排在没降价产品的前面，因为降价产品本身价格是比没降价产品价格高的，所以这样的排序才有意义。

再举个例子，一次考试之后，分数不同的同学按照分数进行排序，分数相同的同学，按照上次考试的分数排序。

再举个例子，一个班的同学，已经按照学号排好序了。现在要按照身高排序。如果是稳定排序排好之后，身高相同的同学，还是按照学号顺序的。

总之，其实就是有两个排序关键字的时候，稳定排序可以让第一个关键字排序的结果服务于第二个关键字排序中数值相等的那些数。

小总结

归并 和 快排 具有相似性，但步骤顺序相反。

  • 归并：线排序左右子数组，然后合并两个有序子数组。
  • 快排：先调配出左右子数组，然后对左右子数组进行合并。

快排先调配左右子数组，就是让左边的数组的所有元素都小于右边数组的所有元素（中间的元素为pivot，就是pivot左边的所有元素都小于pivot，右边的所有元素都大于pivot）。但是左、右的元素在这个时候仍然还是无序的，那么然后对于左、右子数组分别调用排序的函数进行分治。

快排和归并排序都讲完了，这两个是高级排序的面试的重点，一定要细细品味，多过遍数。

  • 堆排序(Merge Sort)

堆插入时间复杂度为O(logN)，取堆顶，最大/小值，时间复杂度为O(1)。但是取完元素之后需要进行Heapify，所以要额外乘上O(n)的时间复杂度，整个的时间复杂度为O(N*logN)

堆排序的过程：

  1. 对元素依次建立最小堆
  2. 依次取堆顶元素，并删除

堆本身是一种很有意思的数据结构，使用数组存储一个树状结构，通过自身的规律，可以用简单的公式获取到当前某个节点的父节点或者左右孩子节点(注意起始坐标是0还是1，公式有区别)。

关键点就是，每次你在调整之前，儿子节点如果大于父亲节点，两者就交换，一直到当前节点小于其他祖宗节点。

非比较类排序

  • 计数排序(Counting Sort)

计数排序要求输入的数据必须是有确定范围的整数。将输入的数据值转化为键存储在额外开辟的数组空间中；然后依次把计数大于1的填充回原数组。总之，你的元素必须是整数，而且元素值不能太大，否则浪费空间。

  • 桶排序(Bucket Sort)

工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。

  • 基数排序(Radix Sort)

按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。先按照个位进行排序，也就是放到0,1,2…9的位置，把低位先排好序。然后再排十位，再按照0-9的值排上去。然后百位，以此类推。这样一来，排序的数组只需要存储0-9的数字，这是比较巧妙的地方。但是基数排序也是有一个短板，就是只能存储整数，不能存储小数的值。

215. Kth Largest Element in an Array(数组中的第K个最大元素)(Mid)

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

1
2
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

1
2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

解：

方法一：暴力，直接先排序再找到第k大的元素

1
2
3
4
5
6
7
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //sort后默认从小到大
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)

但是这个时间复杂度不能让人满意。

方法二：用堆来辅助，可以用一个大顶堆，然后poll() k次，就能找到数组中第k大的了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //默认小顶堆
        // PriorityQueue<Integer> heap = new PriorityQueue<Integer>(
        //     (a,b) ->(a - b) //这个其实不用写，因为默认就是小根堆
        // );
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(); //直接一行搞定即可
        
        for(int num : nums) {
            heap.add(num);
            if(heap.size() > k) {
                heap.poll();
            }
        }
        return heap.poll();
    }
}
  • 时间复杂度：O(Nlogk)，比直接用排序好一些
  • 空间复杂度：O(k)，大小为k的堆，用于存储数据

方法三：快速选择法——借助快速排序的思想

但是，这道题是Mid，Mid如果能用这两个时间复杂度为O(nlogn)的方法能解决，那就不是Mid的难度啦！这里想考察的其实和面试中经常会问到Top K问题中常用的解法之一：基于快排的Partition法，或者叫做快速选择法。

有关Top K问题可以参考这篇文章：如何在10亿数中找出前1000大的数

首先，我们选择一个枢轴(pivot)，并在线性时间内定义其在排序数组中的位置。这可以通过 划分算法 的帮助来完成。

为了实现划分，沿着数组移动，将每个元素与枢轴进行比较，并将小于枢轴的所有元素移动到枢轴的左侧。

这样，在输出的数组中，枢轴达到其合适位置。所有小于枢轴的元素都在其左侧，所有大于或等于的元素都在其右侧。

这样，数组就被分成了两部分。如果是快速排序算法，会在这里递归地对两部分进行快速排序，时间复杂度为 O(N logN)。

而在这里，由于知道要找的第 N - k 小的元素在哪部分中，我们不需要对两部分都做处理，这样就将平均时间复杂度下降到 O(N)。

最终的算法十分直接了当 :

随机选择一个枢轴。

使用划分算法将枢轴放在数组中的合适位置 pos。将小于枢轴的元素移到左边，大于等于枢轴的元素移到右边。

比较 pos 和 N - k 以决定在哪边继续递归处理。

! 注意，本算法也适用于有重复的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {

    public int findKthLargest(int[] nums, int k) {
        int size = nums.length;
        //Kth number is (N-K)th smallest
        // 就是把题目的第k大变成了第k小，k从1开始，若为第1大，则最后返回的是选择之后最后一个与元素
        //比如有9个元素，则第6大就是选择之后第4小的元素，即(size-k)为选择后的第k小
        return quickSelect(nums, 0, size - 1, size - k);
    }
    
    public int quickSelect(int[] nums, int left, int right, int k_smallest) {
        /*
        / returns the k-th smallest of nums within left...right
        */
        //递归结束条件，left和right重合了
        if(left == right) //If the list contains only one element,
            return nums[left]; //return that element
        
        //select a random pivot_index
        // 随机产生一个数轴进行快速选择操作
        Random random_num = new Random();
        int pivot_index = left + random_num.nextInt(right - left);
        
        pivot_index = partition(nums, left, right, pivot_index);
        
        //the pivot is on (N-k)th smallest position
        if(k_smallest == pivot_index)
            return nums[k_smallest];
        else if(k_smallest < pivot_index)
            //这里还是用了快排的分治思想
            return quickSelect(nums, left, pivot_index - 1,k_smallest);
        //go right side
        return quickSelect(nums,pivot_index + 1, right, k_smallest);
    }
    
    public int partition(int[] nums,int left,int right,int pivot_index) {
        int pivot = nums[pivot_index];
        //1. move pivot to end
        swap(nums, pivot_index, right);
        int store_index = left;
        
        // 2.move all smaller elements to the left
        for(int i = left; i <= right; i++) {
            if(nums[i] < pivot) {
                swap(nums, store_index, i);
                store_index++;
            }
        }
        
        //3.move pivot to its final place
        swap(nums, store_index,right);
        
        return store_index;
    }

    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
  • 时间复杂度：平均情况O（N），最坏情况O(N^2)
  • 空间复杂度：O(1)

973. K Closest Points to Origin(最接近原点的K个点)(Mid)

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

1
2
3
4
5
6
7
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

1
2
3
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

解：方法一，直接使用排序。但是因为各个语言的内置sort算法都为快排，所以时间复杂度为O(NlogN)

在计算过程中因为只需要计算到原点之间的距离然后排序，所以可以直接计算每个坐标到0的距离的平方即可。计算之后把排好序的距离对应的点放入到结果数组中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int len = points.length;
        int[] distances = new int[len];
        //先计算并且找到第K近的距离
        for(int i = 0 ; i < len; i++) {
            distances[i] = calc(points[i]);
        }
        Arrays.sort(distances);
        //保存第k大的距离值，后面只要距离值小于这个，就都要返回
        int distanceK = distances[K-1];
        
        int[][] result = new int[K][2];
        //time用来表示当前遍历到了多少，最多不能超过K个
        int time = 0;
        for(int i = 0 ; i < len ; i++) {
            if(calc(points[i]) <= distanceK) {
                result[time++] = points[i];
            }
        }
        return result;
    }
    
    public int calc(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}
  • 时间复杂度：O(NlogN)
  • 空间复杂度：O(N)

方法二：堆排序。时间复杂度和第一个方法一样，因为这里对于前K个返回的元素，最后都是有序的，因为有这个排序的过程，所以时间复杂度最后都是O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[][] kClosest(int[][] points, int K) {
        // 默认小顶堆，即大小为K的堆，最后遍历完了所有元素都是前K小的
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a,b) -> a[0]*a[0] + a[1]*a[1] - b[0]*b[0] - b[1]*b[1]
        );
        for(int[] point : points) {
            heap.add(point);
        }
        int[][] result = new int[K][2];
        for(int i = 0 ; i < K ;i++) {
            result[i] = heap.poll();
        }
        return result;
    }
}

但是在实际LeetCode提交过程中，这个方法二更慢……

方法三：分治法。这个分治过程很相似快排每一轮的partition：随机取一个pivot，将数组中所有比pivot小的数放到pivot左边，比pivot大的数放到pivot右边。然后如果pivot左边的数数量小于K，则继续在右边中找数。

这里的快速排序无需使整个数组有序，只需要筛选出最小的 K 个值即可。

假设第一次排序后，哨兵值 pivot 将原数组分为两个部分：

左侧部分，元素值均小于 pivot，假设下标范围是 [begin, i - 1]，长度为 left_length
右侧部分，元素值均大于或等于 pivot，假设下标范围是 [i + 1, end]，长度为 right_length
此时：

如果 left_length >= K，最小的 K 个值均在左侧，因此下轮递归只需对左侧部分进行排序
如果 left_length < K，我们已经获得了 left_length 个最小值，因此下轮递归只需对右侧部分进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
     public int[][] kClosest(int[][] points, int K) {
        int start = 0;
        int end = points.length - 1;
        while (start < end) {
            # 计算欧几里得距离
            int index = patition(points, start, end);
            if (index == K) {
                break;
            } else if (index < K) {
                start = index + 1;
            } else {
                end = index - 1;
            }
        }

        return Arrays.copyOf(points, K);
    }

    private int patition(int[][] points, int start, int end) {
        int i = start;
        int j = end + 1;
        int mid = distance(points[i][0], points[i][1]);
        while (true) {
            while (distance(points[++i][0], points[i][1]) < mid && i < end);
            while (distance(points[--j][0], points[j][1]) > mid && j > start);
            if (i >= j) {
                break;
            }
            swap(points, i, j);
        }
        swap(points, start, j);
        return j;
    }

    private int distance(int a, int b) {
        return a * a + b * b;
    }

    private void swap(int[][] points, int a, int b) {
        int[] temp = points[a];
        points[a] = points[b];
        points[b] = temp;
    }
}

56. Merge Intervals(合并区间)(Mid)

Given a collection of intervals, merge all overlapping intervals.

Example 1:

1
2
3
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

1
2
3
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

解：注意这里用到的排序的写法，Arrays.sort()里面用了Lambda表达式

先按首位置进行排序;

接下来,如何判断两个区间是否重叠呢?比如 a = [1,4],b = [2,3]

当 a[1] >= b[0] 说明两个区间有重叠.

但是如何把这个区间找出来呢?

左边位置一定是确定，就是 a[0]，而右边位置是 max(a[1], b[1])

所以,我们就能找出整个区间为:[1,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if (intervals == null || intervals.length == 0) return res.toArray(new int[0][]);
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int i = 0;
        while (i < intervals.length) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }
            res.add(new int[]{left, right});
            i++;
        }
        return res.toArray(new int[0][]);
    }
}