Leetcode（215）-数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

思路1：可以用冒泡排序，排一次是最大的元素，排第二次第二大的元素可以就位。时间复杂度为O(kn),n为数组长度。

思路2：快速排序是对冒泡的改进，降低冒泡的递归深度，使时间复杂度降低到O(nlgn)。因为快排每次将数组划分为两组加一个基准元素，每一趟划分你只需要将k与基准元素的下标进行比较，如果比基准元素下标大就从右边的子数组中找，如果比基准元素下标小从左边的子数组中找，如果一样则就是基准元素，找到，如果需要从左边或者右边的子数组中再查找的话，只需要递归一边查找即可，无需像快排一样两边都需要递归，所以复杂度必然降低。

int partition(vector<int>&nums,int low,int high)

{

    int temp=nums[low];

    while(low<high)

    {

        while(low<high && nums[high]<=temp)//注意这里如果low作为一开始基准的选择，要从high那端开始遍历，否则会出错

            high--;

        swap(nums[low],nums[high]);

        while(low<high && nums[low]>=temp)

            low++;

        swap(nums[low],nums[high]);

    }

    return low;

}

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

{

    int low=0;

    int high = nums.size()-1;//这里要注意减1

    while(1)

    {

        int temp = partition(nums,low,high);

        if(k==temp+1)//这里第k大，在数组中的下标却对应的是k-1

            return nums[temp];

        else if(k<temp+1)

        {

            high = temp-1;//这里每次要把基准元素去掉，否则会死循环

        }

        else

        {

            low = temp+1;

        }

    }

}

思路3：最大最小根堆

堆排序是一种树形选择排序方法。堆排序主要分为（1）如何建立堆（2）如何调整堆。我们可以建立最小根堆，用数组的前k个数，建立最小根堆。然后从第k+1开始，和堆顶比较，如果比堆顶大，就交换，交换完重新维护成最小根堆，直到结束。这样堆里存放的就是数组中前k个最大的元素，而堆顶就是这里面最小的，也就是第k大的元素

void HeapAdjust(vector<int>& nums,int s,int length)//调整堆的程序

{

    int temp=nums[s];

    int child = 2*s+1;//这里因为下标从0开始，每个节点的子节点就是2s+1

    while(child<length)

    {

        if(child+1<length && nums[child]>nums[child+1])

            child++;

        if(nums[s]>nums[child])

        {

            nums[s]=nums[child];

            s=child;

            child=2*s+1;

        }

        else

            break;

        nums[s]=temp;//这里的s已经是原来的child了

    }

}

void BuildingHeap(vector<int>& nums,int k)//建立堆，从最后开始筛选

{

    for(int i=(k-1)/2;i>=0;i--)

        HeapAdjust(nums,i,k);

}

//void Heapsort(vector<int>& nums, int k)//堆排序中用到，这里不需要

//{

//    BuildingHeap(nums,k);

//    for(int i=k-1;i>0;i--)

//    {

//        int temp=nums[i];

//        nums[i]=nums[0];

//        nums[0]=temp;

//        HeapAdjust(nums,0,i);

//    }

//}

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

{

    int size=nums.size();

    if(k>size) return nums[size-1];

    vector<int> mynum;

    int index=0;

    for(;index<k;index++)

    {

        mynum.push_back(nums[index]);

    }

    BuildingHeap(mynum,index);

    int j=index;

    for(int i=j;i<size;i++)

    {

        if(nums[i]>mynum[0])

        {

            swap(nums[i],mynum[0]);

            HeapAdjust(mynum,0,index);

        }

    }

    return mynum[0];

}

思路4：用优先队列来实现。常用来代替堆，每次直接加入新数即可，自动维护大小顺序，使用很方便。以大根堆为例，q.top( )是队中最大的数。常用操作还有：q.push_back(x)，q.pop( ) …具体的优先队列使用方法，我下一篇中会仔细总结下。

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

    {

        priority_queue<int, vector<int>, greater<int> > pq;//定义一个递增的

        for(int i = 0; i<nums.size(); i++)

        {

            if (pq.size() == k)//满k个之后,就依次比较后来的元素和其中最小的

            {

                int x = pq.top();

                if (nums[i] > x)//如果比最小的要大，就将最小的抛弃

                {

                    pq.pop();

                    pq.push(nums[i]);

                }

            }

            else

            {

                pq.push(nums[i]);

            }

        }

        return pq.top();//这样最后队列中是前k大的，最小的就是第k大的

    }

思路5、使用multiset，也是利用multiset中的排序功能，而且允许重复

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

    {

        multiset<int> mset;

        int n = nums.size();

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

        {

            mset.insert(nums[i]);

            if (mset.size() > k)

            {

                mset.erase(mset.begin());

            }

        }

        return *mset.begin();

    }

巴特西

Leetcode（215）-数组中的第K个最大元素

最新文章

热门文章