题解 | #寻找第K大#

#include <algorithm>
#include <utility>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型vector
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    int findKth(vector<int>& a, int n, int K) {
        // write code here
        sort(a.begin(), a.end(), [](int a, int b) {
            return a > b;
        });
        return a[K - 1];
    }
};

代码比较短，然后用了匿名函数

自己写算法的就别看了，用一下CPP语法而已

思路都是用分治，然后快排。

要证明在寻找第k大元素的问题中，使用分治法改进的快速选择算法（通常称为“Quickselect”）具有较低的时间复杂度，我们需要从几个角度来考虑。

快速选择算法的基本思想

快速选择算法是一种用于找到数组中第k小（或第k大）元素的选择算法。它基于快速排序的思想，但是与快速排序不同的是，快速选择不需要对整个数组进行排序。具体步骤如下：

1. 选择一个基准值：从数组中随机选择一个元素作为基准值。
2. 分区操作：将数组分为两部分，一部分小于基准值，另一部分大于基准值。
3. 递归查找： 如果k小于左半部分的长度，则在左半部分递归查找第k小的元素。如果k等于左半部分的长度加一，则基准值即为所求的第k小元素。如果k大于左半部分的长度，则在右半部分递归查找第(k-左半部分长度-1)小的元素。

时间复杂度分析

最佳情况

当每次选择的基准值都能将数组均匀分割时，快速选择算法的时间复杂度为O(n)，其中n是数组的长度。这是因为每次分区操作只需要线性时间，并且每次只处理一半的数据。

平均情况

在平均情况下，快速选择算法的时间复杂度也是O(n)。虽然每一次分区不一定能完美地将数组分成相等的两部分，但由于随机选择基准值，平均来看每次分区操作后处理的数据量会减少。

最坏情况

最坏情况下，如果每次选择的基准值都是数组中的最小或最大值，那么每次分区操作只能排除一个元素，导致算法退化到O(n^2)的时间复杂度。然而，通过随机选择基准值可以大大降低这种最坏情况发生的概率。

比较其他算法

• 完全排序：如果使用快速排序或其他O(n log n)排序算法先对整个数组进行排序，然后再访问第k个位置，这显然不是最优的方法，因为其时间复杂度为O(n log n)。我这里用的就是这种
• 堆排序：可以构建一个大小为k的最小堆或最大堆来找到第k大/小的元素，这样做的时间复杂度为O(n + k log n)。对于较大的k，这种方法可能不如快速选择算法高效。
• 线性时间选择算法：存在一些理论上保证线性时间复杂度的算法，如Median of Medians算法，尽管它们在实际应用中由于常数因子较大而可能不如快速选择算法快。