大厂面试：如何用快排思想在O(n)内查找第K大元素？

大厂面试：如何用快排思想在O(n)内查找第K大元素？

1）前置知识：

可以先简单看一下归并和快排的思想：大厂面试：如何用快排思想在O(n)内查找第K大元素？

这里可以简单回顾一下快排的实现：

/**
 * @author: Xiaoqiang-Ladidol
 * @date: 2023/5/27 14:32
 * @description: {}
 */
public class 快速排序 {

    /**
     * quick sort(no stable)
     * best: 0(nlogn)
     * worst: 0(n2)
     * average: 0(nlogn)
     * space: 0(1)
     *
     * @param n
     * @param nums
     */
    public void main_sort(int n, int[] nums) {
        sort(0, n - 1, nums);
    }

    /**
     * 递推公式：
     * quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)
     * 终止条件：
     * p >= r
     *
     * @param p
     * @param r
     * @param nums
     */
    public void sort(int p, int r, int[] nums) {
        if (p >= r) {
            return;
        }
        //获得分区位置
        int q = partition(p, r, nums);
        sort(p, q - 1, nums);
        sort(q + 1, r, nums);
    }

    //分区函数，原地分区
    public int partition(int start, int end, int[] nums) {
        //默认取最后一个元素作为pivot；
        int pivot = end;
        //通过i来遍历增加小于pivot的值：左边小于pivot，右边大于pivot
        int i = start;
        for (int j = start; j < end; j++) {
            if (nums[j] < nums[pivot]) {//求升序
                swap(i++, j, nums);
            }
        }
        swap(i, pivot, nums);
        return i;//此时的pivot已经换位到它的位置了。
    }

    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

2）用快排的思想实现查找数组的第K大元素

O(n) 时间复杂度内求无序数组中的第 K 大元素。比如，4， 2， 5， 12， 3 这样一组数据，第 3 大元素就是 4。

首先解决这个问题，毫无疑问，还是要联想到分治和分区。

我们选择数组区间 A[0…n-1]的最后一个元素 A[n-1]作为 pivot，对数组 A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。注意这里用的是降序快排

如果 p+1=K，那 A[p]就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1]区间，我们再按照上面的思路递归地在 A[p+1…n-1]这个区间内查找。同理，如果 K

Java代码实现：

/**
 * @author: Xiaoqiang-Ladidol
 * @date: 2023/5/26 16:20
 * @description: {}
 */
public class 寻找n中的第k大数字 {
    public int search_main(int n, int[] nums, int k) {
        sort(0, n - 1, nums, k);
        return ans;
    }

    int ans = -1;

    public void sort(int p, int r, int[] nums, int k) {
        if (p >= r) {
            return;
        }
        //获得分区位置
        int q = partition(p, r, nums);
        if (q + 1 == k) {
            ans = nums[q];
        } else if (q + 1 > k) {//注意方向不要找错了
            sort(p, q - 1, nums, k);
        } else {
            sort(q + 1, r, nums, k);
        }
    }

    //分区函数，原地分区
    public int partition(int start, int end, int[] nums) {
        //默认取最后一个元素作为pivot；
        int pivot = end;
        //通过i来遍历增加小于pivot的值：左边小于pivot，右边大于pivot
        int i = start;
        for (int j = start; j < end; j++) {
            if (nums[j] > nums[pivot]) {//求降序
                swap(i++, j, nums);
            }
        }
        swap(i, pivot, nums);
        return i;//此时的pivot已经换位到它的位置了。
    }

    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


}

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
46
47
48
49
50
51
52

实现关键：

1、变成降序方便理解

for (int j = start; j < end; j++) {
    if (nums[j] > nums[pivot]) {//求降序
        swap(i++, j, nums);
    }
}
1
2
3
4
5

2、分区查找

int q = partition(p, r, nums);
if (q + 1 == k) {
    ans = nums[q];
} else if (q + 1 > k) {//注意方向不要找错了
    sort(p, q - 1, nums, k);
} else {
    sort(q + 1, r, nums, k);
}
1
2
3
4
5
6
7
8

3）时间复杂度分析：

你可能会问：为什么上述解决思路的时间复杂度是 O(n)？

第一次分区查找，我们需要对大小为 n 的数组执行分区操作，需要遍历 n 个元素。第二次分区查找，我们只需要对大小为 n/2 的数组执行分区操作，需要遍历 n/2 个元素。依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为 1。

如果我们把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1。这是一个等比数列求和，最后的和等于 2n-1。所以，上述解决思路的时间复杂度就为 O(n)。