LeetCode215. Kth Largest Element in an Array（快速排序）

Medium
Accepted：310,190
Submissions：684,666

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:

You may assume k is always valid, 1 ≤ k ≤ array's length.

链接

https://leetcode.com/problems/kth-largest-element-in-an-array/

题意

在一个乱序的数组中找到第k大的元素。

题解

直接sort一下，时间复杂度$O(nlogn)$
利用快速排序找基准值pivot位置的思想，从大到小排序，在基准值pivot左边的都大于pivot，在基准值pivot右边的都小于pivot，第k大元素的位置为k-1，如果基准值的位置pos等于k-1那么直接返回nums[pos]，如果pos大于k-1那么往左边找，pos小于k-1则往右边找，找到合适的基准值位置那么答案就出来了，平均时间复杂度$T(n) = T(n/2) + n$，即$O(n)$

代码

Runtime: 8 ms, faster than 72.24% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 1.1 MB, less than 28.15% of C++ online submissions for Kth Largest Element in an Array.

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

Runtime: 40 ms, faster than 13.55% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 1.1 MB, less than 81.46% of C++ online submissions for Kth Largest Element in an Array.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        int left = 0, right = len - 1;
        while (true)
        {
            int pos = partition(nums, left, right);
            if (pos == k - 1) // pos位置为第k大数的位置直接返回
                return nums[pos];
            if (pos > k - 1) // pos位置在k-1的右边，往左边找
                right = pos - 1;
            else if (pos < k - 1) // pos位置在k-1的左边，往右边找
                left = pos + 1;
        }
    }

    // 找到基准位置，挖空法
    int partition(vector<int>& nums, int low, int high)
    {
        int ret = low;
        int pivot = nums[ret];
        for (int i = low + 1; i <= high; ++i)
        {
            if (nums[i] > pivot)
            {
                nums[ret] = nums[i];
                nums[i] = nums[++ret];
            }
        }
        nums[ret] = pivot;
        return ret;
    }
};

感觉第二种解决应该是要比第一种快一些的，无需完成整个排序过程，可能leetCode的时间和空间统计有一点问题。

The end.
2019年2月3日星期日