题解 | 寻找第K大

1、解题思路

1. 排序法：直接对整个数组进行排序，然后取第 (n - k) 个元素（假设数组是升序排序）。时间复杂度为 O(nlogn)，空间复杂度为 O(1)（如果使用的是原地排序算法，如堆排序或快速排序）。
2. 快速选择（Quickselect）：类似于快速排序的分区思想，可以在平均 O(n) 时间内找到第 k 大的元素。由于题目要求时间复杂度为 O(nlogn)，且空间复杂度为 O(1)，因此使用排序法更为稳妥。

2、代码实现

C++

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());
        return a[n - K];
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {
        // write code here
        Arrays.sort(a);
        return a[n - K];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param n int整型 
# @param K int整型 
# @return int整型
#
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        a.sort()
        return a[-K]

3、复杂度分析

1. 时间复杂度：O(nlogn)，因为排序的时间复杂度为 O(nlogn)。
2. 空间复杂度：O(1)，因为使用的是原地排序算法。