MENU

LeetCode215. Kth Largest Element in an Array(快速排序)

2019 年 02 月 03 日 • 阅读: 1241 • LeetCode阅读设置

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日 星期日
最后编辑于: 2019 年 03 月 03 日