第 10 关 | 天上的明月——快速排序和归并排序: 2.白银挑战——选择第 K 大的数字-灵析社区

1. 数组第 K 大

数组中的第 k 个最大元素。给定整数数组 nums 和整数 k ，请很返回数组中 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5 
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4

对于这道题，有三种做法，以下我会分别展示3种不同的做法，其实这三种做法大同小异，都是基于快速排序实现的，主要是最后的返回索引可能有所差异。

1.1. 调用 API

这种方法主要是调用 Arrays 中的排序 API ，其底层其是也是基于快速排序实现的，然后返回长度减 k 个元素既可，如果返回最大就减 1，第 2 大就减 2，以此类推。

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

1.2. 手写快排降序

我们再堆部分分析这个过程，这里看看是如何基于快速排序来做的，这个题目出现的频率非常高，甚至在很多时候，面试官直接要求基于快速排序来解决这个问题。而且我们要直接改造一下上面的快排来解决，而不是另起炉灶，只有这样平时的练习才有效果。

为什么能用快速排序来解决呢？我们还是看上面排序的序列： {26,53,48,15,13,48,32,15}

我们第一次选择了26为哨兵，进行一轮的排序过程为：

上面红框位置表示当前已经被赋值给了pivot或者其他位置，可以空出来放移动来的新元素了。我们可以看到26最终被放到了属于自己的位置上，不会再变化，而26的左右两侧可以分别再进行排序。

这里还有一个关键信息，我们可以知道26的索引为3，所以递增排序之后26一定是第 4大的元素。这就是解决本问题的关键，既然知道26是第4大，那如果我要找第2大，一定是要到右边找。如果要找第6大，一定要到左边找（当然，如果降序排序就反过来了），而不需要的那部分就不用管了。这就是为什么能用快速排序解决这个问题。

我们采用降序排列：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort2(nums,0,nums.length - 1);
        return nums[k - 1];
    }
    public static void quickSort2(int[] nums, int l, int r) {
        int start = l;
        int end = r;
        int pivot = nums[start + end >> 1];
        // 每次循环都将大的放到左边，然后将小的部分放到右边
        while(l < r){
            while(nums[start] > pivot){
                start++;
            }
            while(nums[end] < pivot){
                end--;
            }
            // 如果 l >= r 说明左边的值全部大于等于mid的值，右边全是小的，直接退出
            if(start >= end){
                break;
            }
            // 交换元素
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            if(nums[start] == pivot){
                end--;
            }
            if(nums[end] == pivot){
                start++;
            }
        }
        //退出循环防止栈溢出
        if(start == end){
            start++;
            end--;
        }
        if(l < end){
            quickSort2(nums,l,end);
        }
        if(r > start){
            quickSort2(nums,start,r);
        }
    }
}

然后就是尽量能套用自己练习过的底阿妈，否则核心逻辑都要考虑相反的情况，会导致我们面试的时候现场书写变得非常困难。

1.3. 升序代码

然后在这里我也放一下升序的代码：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums,0,nums.length - 1);
        return nums[nums.length -k];
    }
    public static void quickSort(int[] q, int l, int r) {
        if (l >= r) return;
        int x = q[l+r>>1];

        //Define positions of two pointers
        int i = l - 1;
        int j = r + 1;

        while (i < j) {
            do i++; while (q[i] < x);
            do j--; while (q[j] > x);
            //do Swap
            if (i < j) {
                int temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }

        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }
}

阅读量：861

点赞量：0

收藏量:0