LeetCode 215.第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

算法1

(排序) $O(nlogn)$

最直观的思路是先排序然后选择，那么无论使用什么排序方法最快都是 $O(nlogn)$ 的时间复杂度，代码如下

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        quick_sort(nums, 0, n - 1);

        return nums[n - k];
    }

    void quick_sort(vector<int>& a, int l, int r)
    {
        if( l >= r) return ;

        int i = l - 1, j = r + 1;
        int x = a[(l + r) >> 1];

        while( i < j)
        {
            do i ++; while( a[i] < x);
            do j --; while( a[j] > x);

            if( i < j)
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        quick_sort(a, l, j);
        quick_sort(a, j + 1, r);
    }
};