每日题解:LeetCode 215. 数组中的第K个最大元素

Author Avatar
清水雅然君 06月 30,2020

题目地址
个人博客地址

题目描述

在未排序的数组中找到第 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 ≤ 数组的长度。

解法

JAVA

class Solution {
    public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k);
    for (int num : nums) {
        if (heap.size() < k){
            heap.offer(num);
        } else {
            if (num > heap.peek()){
                heap.poll();
                heap.offer(num);
            }
        }
    }
    return heap.peek();
    }
}

CPP

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
         int left=0,len=nums.size(),right=len-1;
        int target=len-k;
        int ans;
        while ((ans = partition(nums, left, right)) != target ) {
            if(ans<target){
                left=ans+1;
            }else if(ans>target){
                right=ans-1;
            }
        }
        return nums[ans];
    
    }

     int partition(vector<int> &vector, int left, int right) {
        int temp=vector[left];
        int leftIndex=left;
        for (int i = left+1; i <= right; ++i) {
            if(vector[i]<temp){
                leftIndex++;
                swap(vector, leftIndex, i);
            }
        }
        swap(vector, leftIndex, left);
        return leftIndex;
    }
     void swap(vector<int> &vector, int left, int right) {
        int temp=vector[left];
        vector[left]=vector[right];
        vector[right]=temp;
    }
    
};

解题思路

优先队列

这里是直接调用JAVA的API实现最小堆的做法,PriorityQueue(优先队列)优先队列的作用是能保证每次取出的元素都是队列中权值最小,即默认栈顶是最小元素
将元素的排序交给PriorityQueue进行维护,由于需要找到第K个最大元素,就是从大到小进行排序数组,找到倒数第k个元素,只要维护一个只有k大小的最小堆就可以了

  1. 遍历数组,
  2. 当堆的元素个数小于k时,直接添加到堆中
  3. 当堆的元素个数大于k时,当遍历的元素大于堆顶元素时,堆顶元素弹出,然后添加当前遍历的数组
 for (int num : nums) {
        if (heap.size() < k){
            heap.offer(num);
        } else {
            if (num > heap.peek()){
                heap.poll();
                heap.offer(num);
            }
        }
    }

减治法

这部分代码参考了李哥的题解
假设nums[target]是目标答案下标值,通过某方法将下标范围存放[0,target-1]nums[target]小的值,比nums[target]大的值放在[target+1,nums..size()]范围内,由于答案是第k大的元素,按照自然顺序进行排序的,应该是target=nums..size()-k,当我们按照target左小右大思路存放数组元素,nums[target]就是我们最终的答案

  1. nums[0] 到 nums[target - 1] 中的所有元素都不大于 nums[target];
  2. nums[target + 1] 到 nums[,nums..size()]] 中的所有元素都不小于 nums[target]
    我们以[3,2,1,5,6,4] 为例,第一次寻找比num[0]小的元素,下标停在元素1的位置
    在这里插入图片描述
    此时,leftIndex-1左边应该都是比num[0]小元素,leftIndex+1右边都是num[0]大的元素,这是我们还需要num[0]和leftIndex进行互换,
    在这里插入图片描述
    换个思路寻找第K个最大元素,其实就寻找第 target=nums.size()- k元素,我们只要保证target元素左小右大就可以了
    这里我是将排序和赋值放到了whlie循环条件中,完成了排序和判断,当然也可以使用whlie(true)形成死循环阻塞,在while循环内进行赋值
int left = 0, len = nums.size(), right = len - 1;
        int target = len - k;
        int ans;
        while ((ans = partition(nums, left, right)) != target) {
            if (ans < target) {
                left = ans + 1;
            } else if (ans > target) {
                right = ans - 1;
            }
        }
        return nums[ans];

这里其实是快速排序的思路,每次我们选择一个数作为标记,待排序结束后,将标记存到其正确的位置

int partition(vector<int> &vector, int left, int right) {
        int temp = vector[left];
        int leftIndex = left;
        //遍历元素,发现当前元素比目前的元素小的就进行元素值互换,并且leftIndex下标往后移动,保存下一个比temp元素
        for (int i = left + 1; i <= right; ++i) {
            if (vector[i] < temp) {
                leftIndex++;
                swap(vector, leftIndex, i);
            }
        }
        //这里就是最后需要将当前值放到leftIndex位置上,这里其实就是图中所示的3和1的位置互换
        swap(vector, leftIndex, left);
        return leftIndex;
    }