GuilinDev

Lc0215

05 August 2008

215 Kth Largest Element in an Array

原题概述

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大的值，元素可以有重复。这里有总结的topk的办法，总共有四个逐渐优化的办法：

1）全局排序，将整个数组排序后取第k-1个数，O(nlogn)；

2）局部排序，只排最大的k个数，利用冒泡排序的办法（因为能知道kth的位置），冒泡一次，找出一个最大值，冒k次就找到第kth的最大值了，O(n*k)；

3）利用heap，创建一个最小堆用来存储当前最大的k个元素

接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。

直到，扫描完所有n-k个元素，最终堆中的k个元素，就是猥琐求的TopK。复杂度 O(n*lg(k))。

4）随机选择，利用快排中partition的思想，这里以找到topk的所有数举例来说明

首先看看快排的伪代码

1
2
3
4
5
6
7
8
9
10
11

void quick_sort(int[]arr, int low, inthigh){

    if(low== high) return;

    int i = partition(arr, low, high);

    quick_sort(arr, low, i-1);

    quick_sort(arr, i+1, high);

}

其核心算法思想是，分治法。

分治法（Divide & Conquer），把一个大的问题，转化为若干个子问题（Divide），每个子问题“都”解决，大的问题便随之解决（Conquer）。这里的关键词是“都”。从伪代码里可以看到，快速排序递归时，先通过partition把数组分隔为两个部分，两个部分“都”要再次递归。

分治法有一个特例，叫减治法。

减治法（Reduce & Conquer），把一个大的问题，转化为若干个子问题（Reduce），这些子问题中“只”解决一个，大的问题便随之解决（Conquer）。这里的关键词是“只”。

二分查找binary_search，是一个典型的运用减治法思想的算法，其伪代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int BS(int[]arr, int low, inthigh, int target){

    if(low> high) return -1;

    mid= low +(high - low) / 2;

    if(arr[mid]== target) return mid;

    if(arr[mid]> target)

        return BS(arr, low, mid-1, target);

    else

        return BS(arr, mid+1, high, target);

}

二分查找，一个大的问题，可以用一个mid元素，分成左半区，右半区两个子问题。而左右两个子问题，只需要解决其中一个，递归一次，就能够解决二分查找全局的问题。

通过分治法与减治法的描述，可以发现，分治法的复杂度一般来说是大于减治法的：

快速排序：O(n*lg(n))

二分查找：O(lg(n))

回到快速排序，它的核心是：

1

i = partition(arr, low, high);

这个partition是干嘛的呢？

顾名思义，partition会把整体分为两个部分。

更具体的，会用数组arr中的一个元素（默认是第一个元素t=arr[low]）为划分依据，将数据arr[low, high]划分成左右两个子数组：

  • 左半部分，都比t大
  • 右半部分，都比t小
  • 中间位置i是划分元素

以上述TopK的数组为例，先用第一个元素t=arr[low]为划分依据，扫描一遍数组，把数组分成了两个半区：

  • 左半区比t大
  • 右半区比t小
  • 中间是t

partition返回的是t最终的位置i。

很容易知道，partition的时间复杂度是O(n)，也就是把整个数组扫一遍，比t大的放左边，比t小的放右边，最后t放在中间N[i]。

partition和TopK问题有什么关系呢？

TopK是希望求出arr[1,n]中最大的k个数，那如果找到了第k大的数，做一次partition，不就一次性找到最大的k个数了么？（ 本例即partition后左半区的k个数）

问题变成了arr[1, n]中找到第k大的数。

再回过头来看看第一次partition，划分之后：

i = partition(arr, 1, n);

  • 如果i大于k，则说明arr[i]左边的元素都大于k，于是只递归arr[1, i-1]里第k大的元素即可；
  • 如果i小于k，则说明说明第k大的元素在arr[i]的右边，于是只递归arr[i+1, n]里第k-i大的元素即可；

这就是随机选择算法randomized_select，属于上面说的减治法，伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int RS(arr, low, high, k){

    if(low== high) return arr[low];

    i= partition(arr, low, high);

    temp= i-low; //数组前半部分元素个数

    if(temp>=k)

        return RS(arr, low, i-1, k); //求前半部分第k大

    else

        return RS(arr, i+1, high, k-i); //求后半部分第k-i大

}

这是一个典型的减治算法，递归内的两个分支，最终只会执行一个，它的时间复杂度是O(n)。

再次强调一下：

  • 分治法，大问题分解为小问题，小问题都要递归各个分支，例如：快速排序
  • 减治法，大问题分解为小问题，小问题只要递归一个分支，例如：二分查找，随机选择

通过随机选择（randomized_select），就能找到arr[1, n]中第k大的数；

如果再进行一次partition，就能得到所有TopK的结果。

BFPRT可以对时间进一步优化，但空间复杂度高。

代码

利用冒泡排序，进行局部排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int findKthLargest(int[] nums, int k) {
        for (int i = 0; i < k; i++) {//冒泡排序外循环控制排序的趟数，排好k个数
            for (int j = nums.length - 1; j > i; j--) {//冒泡排序内循环控制每次排序涉及的元素的个数
                if (nums[j] > nums[j - 1]) {//先放大的在前面，小的放后面去
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }
            }
        }
        return nums[k-1];//第k-1个元素是第k大的数
    }
}

利用Heap，只选择topK，不排序topK，O(n*log(K))，需要把所有n个数字放入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //建立一个k个元素的最小堆，最后的堆顶就是第k大
        PriorityQueue<Integer> heap = new PriorityQueue<>(k);

        //先把前k个元素存入，作为初始值
        for (int i = 0; i < k; i++) {
            heap.offer(nums[i]);
        }

        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap.peek()) {//如果新来的元素大于堆顶的元素
                heap.poll();//移除刚才较小的头部
                heap.offer(nums[i]); // 添加较大的元素
            }
        }
        return heap.peek();//返回队列头部
    }
}

快速选择, O(k*log(k) + 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

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //传入的参数nums.length - k表示找到nums.length - k最小的
        return findK(nums, nums.length - k, 0, nums.length - 1);
    }

    private int findK(int[] nums, int k, int left, int right) {
        if (left >= right) {//递归的终止条件，表示已经递归找完整个数组
            return nums[left];
        }

        int i = partition(nums, left, right);
        if (i == k) {//恰好是第k大的数
            return nums[i];
        } else if (i < k) {//在选定的pivot右边
            return findK(nums, k, i + 1, right);
        } else {//左边
            return findK(nums, k, left, i - 1);
        }
    }

    //只partition一次
    private int partition(int[] nums, int start, int end) {
        int pivot = nums[start];//基准
        int slow = start;//开始
        int fast = start + 1;//从start位置后面一位元素准备开始swap

        while (fast <= end) {//到最后一个元素前
            if (nums[fast] < pivot) {//将小的元素挪到pivot前面
                slow++;//这里需要先让指向pivot索引后移一位
                swap (nums, slow, fast);
            }
            fast++;//可能的交换结束后，fast继续右移
        }
        swap (nums, start, slow);//最后需要交换一下初始位置元素和pivot索引的元素
        return slow;//pivot所处的位置
    }

    private void swap (int[] nums, int i, int j) {
        // 这里用三次异或不行
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
This site is open source. Improve this page.