215. Kth Largest Element in an Array

yPhantom 2019年10月14日 30次浏览

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:

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

Example 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.

Solution

题意让找到数组中第K大的数,我们可以理解为找到第n-k+1小的数。

最简单的方法可以通过数组排序:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

这里简单说一下Arrays.sort使用的排序方法是O(n logn)的时间复杂度和O(1)的空间复杂度。当然还有一些比较有趣的解法,可以查看Discuss

这里主要说一种就是快速选择。

什么是快速选择?

可以查看一下维基百科,我们知道,快速排序是设置一个标杆,左右两边同时逼近,右边先动,每一轮循环都将比标杆小的放在左边,比标杆大的放在右边,这样产生的结果中每轮标杆的位置都是正确的。

快速选择就是快速排序的简化,根据每轮得到的标杆的位置,如果标杆前有n-1个数,则标杆是第n小的,如果标杆前的数不足n,则去n之后的数中递归的进行快速选择。

代码如下:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int quickSelect(int[] nums, int left, int right, int k) {
        int pivot = nums[right];
        int start = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] < pivot) {
                swap(nums, start++, i);
            }
        }
        
        swap(nums, start, right);
        
        if (start == k) {
            return nums[start];
        } else if (start < k) {
            return quickSelect(nums, start + 1, right, k);
        } else {
            return quickSelect(nums, left, start - 1, k);
        }
    }
    
    private void swap(int[] a, int left, int right) {
        int tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
    }
}

注意,快排的时间复杂度是O(nlogn),快速选择的时间复杂度是O(n),两者的最坏时间复杂度都是O(n2)