题目

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.

For example,

Given [3,2,1,5,6,4] and k = 2, return 5.

Note:

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

分析

题目大意：

从一个未经排序的数组中找出第k大的元素。注意是排序之后的第k大，而非第k个不重复的元素

可以假设k一定是有效的， 1 ≤ k ≤ 数组长度

直观的解题方法便是利用排序，然后直接返回nums[len-k]即可，利用库函数sort可实现，T(n)=O(nlogn)；

直接用上述方法必然不是该题目的考察目的，该题目引出一个O(n)解法——快速选择（QuickSelect）算法耶鲁大学关于QuickSelect算法的介绍

AC代码

class Solution {

public:

    //方法一：直观解法 时间复杂度O(nlogn)

    int findKthLargest1(vector<int>& nums, int k) {

        int len = nums.size();

        if (len <= 0 || k > len || k < 0)

            return INT_MIN;

        sort(nums.begin(), nums.end());

        return nums[len - k];

    }

    //方法二：快速选择算法，利用两个辅助数组

    int findKthLargest(vector<int>& nums, int k) {

        int len = nums.size();

        if (len <= 0 || k > len || k < 0)

            return INT_MIN;

        vector<int> A1, A2;

        int idx = rand() % len;

        int key = nums[idx];

        for (int i = 0; i < len; ++i)

        {

            if (nums[i] < key)

                A1.push_back(nums[i]);

            else if (nums[i] < key)

                A2.push_back(nums[i]);

            else

                continue;

        }//for

        if (k <= A1.size())

            return findKthLargest(A1, k);

        else if (k > (len - A2.size()))

            return findKthLargest(A2, k - (len - A2.size()));

        else

            return key;

    }

};

GitHub测试程序源码