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<=||n>(int)nums.size())

    {

        return NULL;

    }

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

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

    return nums[n-];

}

挑战：要求时间复杂度为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=;

    int right=nums.size()-;

    while()

    {

        int result=quickSort(nums,left,right);

        if (result==n-)

        {

            return nums[result];

        }

        else if (result>n-)

        {

            right=result-;

        }

        else

        {

            left=result+;

        }

    }

    }

    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 ？没看懂……

巴特西

5 第k大元素

注意事项

最新文章

热门文章