215. Kth Largest Element in an Array

• O(NlogN)的时间复杂度+O(1)的空间复杂度

思路:先排序，然后输出第k大的元素即可，排序的时间复杂度是O(NlogN)，输出第k大元素的时间复杂度为O(1)

class Solution
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        sort(nums.begin(), nums.end(), std::greater<>{});
        return nums[k - 1];
    }
};

• Quick Sort 的思想

代码实现：

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

        while (true)
        {
            int pos = partition(nums, left, right);  //pos是Pivot在nums中的位置
            if (pos == k - 1)
            {
                return nums[pos];
            }
            else if (pos > k - 1)
            {
                right = pos - 1;
            }
            else
            {
                left = pos + 1;
            }
            //else if (pos > k - 1)
            //{
            //  //更新左边
            //  /*left = pos + 1;*/
            //  right = pos - 1;
            //}
            //else  //nums[pos] < nums[k - 1]
            //{
            //  //更新右边
            //  /*right = pos - 1;*/
            //  left = pos + 1;
            //}
        }
    }
private:
    int partition(vector<int>& nums, int left, int right)
    {
        int pivot = nums[left];  //选最左边一个元素作为pivot
        
        int l = left + 1;
        int r = right;

        while (l <= r)
        {
            if (nums[l] < pivot && nums[r] > pivot)
            {
                std::swap(nums[l],nums[r]);
                l++;
                r--;
            }
            if (nums[l] >= pivot)
            {
                l++;
            }
            if (nums[r] <= pivot)
            {
                r--;
            }
        }

        std::swap(nums[left],nums[r]);
        return r;
    }
};

看了第二个方法，我觉得我可能学了一个假的快排，不，我根本就没学过快排。

• 参考资料：
  1 https://www.cnblogs.com/grandyang/p/4539757.html 《[LeetCode] 215. Kth Largest Element in an Array 数组中第k大的数字》

215. Kth Largest Element in an Array

原文：https://www.cnblogs.com/Manual-Linux/p/12031595.html