简单问题的特殊解法 LeetCode 215. 数组中的第K个最大元素

题目

链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array
在未排序的数组中找到第 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 ≤ 数组的长度。

代码模板

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        
    }
};

二分查找

解析

可以使用二分查找,查找目标是[left,right]之间第一个大于自身的其他元素个数小于k的数,这个数即为数组排序后的第 k 个最大的元素。
算法的时间复杂度为O(nlogn),和直接排序、最小堆的耗时差不多。
优点:

  • 空间复杂度O(1)
  • 不改变原数组

代码

class Solution
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        auto minmax = minmax_element(nums.begin(), nums.end());
        int left = *minmax.first;
        int right = *minmax.second;

        int mid;
        int countGreat;
        while (left < right)
        {
            mid = left + (right - left) / 2;
            countGreat = count_if(nums.begin(), nums.end(), [mid](int n) { return n > mid; });
            if (countGreat >= k)
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }

        return left;
    }
};
# leetcode  C++  数组 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×