5 第k大元素

原题网址：http://www.lintcode.com/zh-cn/problem/kth-largest-element/

在数组中找到第k大的元素

注意事项

你可以交换数组中的元素的位置

您在真实的面试中是否遇到过这个题？

Yes

样例

给出数组 [9,3,2,4,8]，第三大的元素是 4

给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推

挑战

要求时间复杂度为O(n)，空间复杂度为O(1)

标签

排序快速排序

非挑战AC代码：

int kthLargestElement1(int n, vector<int> &nums)
{
    if (n<=0||n>(int)nums.size())
    {
        return NULL;
    }
    sort(nums.begin(),nums.end());
    reverse(nums.begin(),nums.end());
    return nums[n-1];
}

挑战：要求时间复杂度为O(n)，空间复杂度为O(1)

参考 https://blog.csdn.net/lhanchao/article/details/52087101

对数组利用快速排序从大到小排序的思想，找到每一次快速排序时基准数的下标（基准数的下标即为排序好后该数的真实下标），直到找到下标为k-1的数为止。（具体怎么算时间复杂度我也不太清楚，还要学习，网上说这种算法的时间复杂度为O(n)）

class Solution {
public:
    /*
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    int kthLargestElement(int n, vector<int> &nums) {
        // write your code here
        if (n>(int)nums.size())
    {
        return NULL;
    }
    int left=0;
    int right=nums.size()-1;
    
    while(1)
    {
        int result=quickSort(nums,left,right);
        if (result==n-1)
        {
            return nums[result];
        }
        else if (result>n-1)
        {
            right=result-1;
        }
        else
        {
            left=result+1;
        }
    }
    }
    
    int quickSort(vector<int> &nums,int left,int right)
{
    int i=left;
    int j=right;
    int temp=nums[i];
    while (i<j)
    {
        while(i<j&&temp>=nums[j])
        {
            j--;
        }
        if (i<j)
        {
            nums[i]=nums[j];
            i++;
        }
        while(i<j&&temp<nums[i])
        {
            i++;
        }
        if (i<j)
        {
            nums[j]=nums[i];
            j--;
        }
    }
    nums[i]=temp;
    return i;
}
};

其他参考：白话经典算法系列之六快速排序快速搞定

https://blog.csdn.net/wangyuquanliuli/article/details/47758327

https://www.cnblogs.com/libaoquan/p/6807803.html ？没看懂……