215. Kth Largest Element in an Array

Leetcode link

解题思路

本题要求我们求出一个数组中第 k 大的数字

一个最简单的方法当然是排序后直接返回下标为 k-1 的数字，但是这样时间复杂度就来到了 O(nlogn)

总所皆知，排序算法在某些情况下是可以来到 O(n) 的复杂度的，那我们有没有办法根据题目的限制来缩小计算范围呢？

答案是肯定的，我们可以使用快速排序的思想来求解：

• 快速排序（降序版本）的优点在于，每一次的排序总能确定选中那个数字的排序后下标，且每次排序后，该数字左边必比它大；右边必比它小
• 套用到这一题，我们只要当快速排序选中的下标刚好等于 k-1 就符合要求了，剩下的部分不需要计算
• 就算运气不好选中的下标不是 k-1，我们也可以快速定位到下一次快排的范围，进而加速整个算法

C++

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size()-1, k - 1);
    }

    int quickSelect(vector<int>& nums, int left, int right, int index) {
      // 每次快排结束后检查一下下表是否是 k-1
        int position = partition(nums, left, right);
        if(position == index) {
            return nums[position];
        }else {
          // 如果不是则可以选取对应的下标范围再做快排
            return index < position ? quickSelect(nums, left, position - 1, index) : quickSelect(nums, position + 1, right, index);
        }
    }

  // 改良版的单次快排，返回选中数字的最终下标
    int partition(vector<int>& nums, int left, int right) {
        int num = nums[left];
        int i = left + 1;
        for(int j=left + 1;j<=right;j++) {
            if(nums[j] > num) {
                swap(nums[i++], nums[j]);
            }
        }
        swap(nums[left], nums[i - 1]);
        return i-1;
    }
};

Javascript

var findKthLargest = function(nums, k) {
    return quickSelect(nums, 0, nums.length - 1, k - 1);
};

var quickSelect = function(nums, left, right, index){
    let position = partition(nums, left, right);
    if(index === position) {
        return nums[position];
    } else {
        return index > position ? quickSelect(nums, position + 1, right, index) : quickSelect(nums, left, position - 1, index);
    }
}

var partition = function(nums, left, right){
    let num = nums[left];
    let i = left + 1;
    for(let j = left + 1;j<=right;j++) {
        if(nums[j] > num) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }
    [nums[left], nums[i - 1]] = [nums[i - 1], nums[left]];
    return i-1;
}