【LeetCode】【算法】215. 数组中的第K个最大元素

LeetCode 215. 数组中的第K个最大元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
你必须设计并实现时间复杂度为O(n)的算法解决此问题。
示例:
输入: [3,2,1,5,6,4], k = 2
输出: 5

思路

思路：基于快速排序来做，第K个最大元素也就是从小到大的第nums.length-K个元素

1. 每次以最左边的元素为pivot，对数组进行排序；
2. 如果恰巧这个pivot最后的交换位置就是nums.length-K，那就可以找到这个元素了；
3. 不满足上述条件的话，若交换位置loc<nums.length-K，则在[0,nums.length-K-1]中找；否则在[nums.length-K+1,nums.length-1]中找

代码

class Solution {
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public int quickSortFast(int[] nums, int left, int right, int k){
        // 让最左侧数字作为pivot
        int partition = nums[left];

        // 定义变量用于双路快排
        int l = left + 1, r = right;
        // 进行快排的操作
        while (true) {
            while (l <= r && nums[l] < partition) l++;
            while (r >= l && nums[r] > partition) r--;
            if (l > r) break;
            swap(nums, l, r);
            l++;
            r--;
        }

        // 交换回来
        swap(nums, left, r);

        // 如果不是第k大，继续递归
        if (r < k){
            return quickSortFast(nums, r + 1, right, k);
        } else if (r > k){
            return quickSortFast(nums, left, r - 1, k);
        } else {
            return partition;
        }
    }
    public int findKthLargest(int[] nums, int k) {
        // 基于快排来做
        /**
            * 快排思想：
            * 1. 选择一个随机置作为pivot
            * 2. 以这个pivot为边界，区分出左和右
            * 3. 判断pivot是否是第k大的，如果不是第k大的，根据当前所处的位置index，判断往左边找还是往右边找
            * 4. 循环以上思路得到最后结果
            * */
        // 最后输入nums.length - k，是因为实际上上面是求从小->大第k个元素
        // 要求第k大的元素，实际上就是从小->大第nums.length - k个元素
        return quickSortFast(nums, 0, nums.length - 1, nums.length - k);
    }
}

注意这里快速排序用了一个东西叫做双路快排，但是核心思想并不难。初始化是l=left+1,r=right，也就是速度两端，接着用一个while(true)做循环，在循环内部判断if(l>r)则跳出循环
在循环内部，对于l，找到nums[l]>partition的数，等待做交换，故while(l<r&&nums[l]<partition) l++;
在循环内部，对于r，找到nums[i]<partition的数，等待做交换，故while(l<r&&nums[r]>partition) r--;
注：上面两个循环实际上就是为了找到从左边起第一个比partition大的数、和右边起第一个比partition小的数做交换。比起普通的一个一个遍历看是否交换节省了不少时间，因为这里相当于一个双指针的操作
找到了以后，交换l和r位置上的值：swap(nums,l,r)
最后l++,r--，让两个指针往下一个位置移动