您的位置: 首页  >  IT文章  >  【LeetCode-数组】数组中的第K个最大元素

【LeetCode-数组】数组中的第K个最大元素

分类: IT文章 • 2022-05-22 22:39:40

题目描述

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

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

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

说明：

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

题目链接： https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

思路1

升序排序，然后输出第 n-k 个元素（第 k 大）。代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()-k];
    }
};
  • 时间复杂度：O(nlogn)
    快速排序的时间复杂度。
  • 空间复杂度：O(1)

思路2

使用小根堆，小根堆的堆顶元素是堆中最小的元素。所以，我们遍历数组，将数组中的元素加入堆中，然后保持堆的大小为 k，这样数组遍历结束后的堆中的元素就是数组中前 k 大的元素，堆顶元素是堆中最小元素，也就是第 k 大的元素。代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> q;
        for(int i=0; i<nums.size(); i++){
            q.push(nums[i]);
            if(q.size()>k) q.pop();
        }
        return q.top();
    }
};
  • 时间复杂度：O(nlogk)
    向堆中添加一个元素的时间复杂度为 logk，添加 n 次，所以为 nlogk。
  • 空间复杂度：O(k)

思路3

使用快速排序中的 partition 过程来做。partition 过程如下：

  • 找一个比较的基准，例如选取数组的第一个元素；
  • 设置两个指针 i=0，j=nums.size()-1；
  • 如果 i<j，循环：
    • 从数组尾从后向前遍历，找到第一个小于基准的元素 nums[i]；
    • 从数组头从前向后遍历，找到第一个大于基准的元素 nums[j]；
    • 交换 nums[i] 和 nums[j]；
  • 交换 nums[i] 和 nums[left]。

一次 partition 之后，nums[i] 之前的数字都小于等于 nums[i]，nums[i] 之后的数字都大于等于 nums[i]，nums[i] 的位置已经确定，也就是 nums[i] 是数组 nums 中第 i 小的元素，如果 i==nums.size()-k（第 k 大元素），则返回 nums[i]，否则根据 i 和 nums.size()-k 的大小关系，使用类似于二分查找的方法缩小 partition 的范围。具体代码如下：

class Solution {
public:
    int ans = -1;
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0;
        int right = nums.size()-1;
        int target = nums.size()-k;
        while(true){    // 注意这里的条件是 while(true)，不是 while(left<right)
            int idx = partition(nums, left, right);
            if(idx==target) return nums[idx];
            else if(idx<target){
                left = idx+1;
            }else if(idx>target){
                right = idx-1;
            }
        }
        return -1;
    }

    int partition(vector<int>& nums, int left, int right){
        int base = nums[left];
        int i = left;
        int j = right;
        while(i<j){
            while(nums[j]>=base && i<j) j--;
            while(nums[i]<=base && i<j) i++;
            swap(nums[i], nums[j]);
        }
        swap(nums[i], nums[left]);
        return i;
    }
};

注意，循环条件是while(true)，不是while(left<right)。
这种写法参考了这篇题解。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

相关推荐