小学生都能看懂的题解 | #寻找第K大#

解决方法：

我们可以通过一种叫做“快速选择”的游戏来找到这张卡片。这个游戏有点像快速排序，但我们的目标不是完全排序所有的卡片，而是找到那张特定的卡片。

游戏规则如下：

1. 选择一张参考卡片：
1. 从你的卡片堆里随便挑一张出来作为参考卡片。
2. 比较并分堆：
1. 把所有比参考卡片大的卡片放在一堆。
2. 把所有比参考卡片小的卡片放在另一堆。
3. 把等于参考卡片的卡片放在中间。
3. 判断并缩小范围：
1. 如果第K大的卡片在这堆卡片中排在比参考卡片大的那一堆中，我们就只关注比参考卡片大的那堆卡片，然后重复上面的游戏。
2. 如果第K大的卡片在这堆卡片中排在与参考卡片相同的一堆中，那么参考卡片就是我们要找的答案。
3. 如果第K大的卡片在这堆卡片中排在比参考卡片小的那一堆中，我们就只关注比参考卡片小的那一堆卡片，并且调整K的值（因为现在我们不再计算比参考卡片大的那些卡片）。
4. 重复游戏：
1. 一直重复这个游戏，直到我们找到那张第K大的卡片为止。

示例：

想象一下，你有这样一堆卡片：[10, 10, 9, 9, 8, 7, 5, 6, 4, 3, 4, 2]，你要找到第三大的卡片。

1. 假设你随便选了一张卡片9作为参考卡片。
2. 比较后，你会得到这样的三堆卡片：
1. 比9大的：[10, 10]
2. 等于9的：[9, 9]
3. 比9小的：[8, 7, 5, 6, 4, 3, 4, 2]
3. 因为我们要找第三大的卡片，而第三大的卡片肯定不在比9小的那堆里，也不在等于9的那堆里（因为这里有两张9）。所以我们只需要在比9大的那堆里继续玩这个游戏。
4. 在[10, 10]这一堆里，很明显第三大的就是9。

这样，通过这个游戏，我们找到了第三大的卡片是9。

下面来看具体的代码实现：

import java.util.Arrays;

public class Solution {

    /**
     * 根据快速排序的思路，找出数组中第 K 大的数。
     *
     * @param a 整型数组
     * @param n 数组的长度
     * @param K 要查找的第 K 大的位置
     * @return 第 K 大的整数
     */
    public int findKth(int[] a, int n, int K) {
        // 调用快速选择方法，传入数组、数组长度、以及要找的第K大元素的位置（减1是因为数组索引从0开始）
        return quickSelect(a, 0, n - 1, K - 1);
    }

    /**
     * 对数组进行分区操作。
     *
     * @param arr 数组
     * @param low 起始位置
     * @param high 结束位置
     * @return 基准元素的新位置
     */
    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low - 1; // 初始化较小元素的索引
        
        // 遍历数组，除了最后一个元素
        for (int j = low; j < high; j++) {
            if (arr[j] > pivot) { // 如果当前元素大于基准
                i++; // 更新较小元素的索引
                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // 将基准元素放到正确的位置上
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // 返回基准元素的新位置
    }

    /**
     * 快速选择算法的实现。
     *
     * @param arr 数组
     * @param left 当前子数组的左边界
     * @param right 当前子数组的右边界
     * @param k 要查找的第 k 大的元素的位置
     * @return 第 k 大的元素
     */
    private int quickSelect(int[] arr, int left, int right, int k) {
        if (left == right) {
            // 如果只有一个元素，直接返回该元素
            return arr[left];
        }

        int pivotIndex = partition(arr, left, right); // 执行分区操作

        if (k == pivotIndex) {
            // 如果 k 等于基准元素的位置，基准元素即为第 k 大的元素
            return arr[pivotIndex];
        } else if (k < pivotIndex) {
            // 如果 k 在基准元素的左侧，继续在左侧查找
            return quickSelect(arr, left, pivotIndex - 1, k);
        } else {
            // 如果 k 在基准元素的右侧，继续在右侧查找
            return quickSelect(arr, pivotIndex + 1, right, k);
        }
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。