LeetCode 215：数组中的第K个最大元素

小半 • 2023年2月3日上午10:51 • 技术随笔 • 阅读 179

题目：

思路：

题目说不是第k个不同的元素，即重复的元素算多个，类似rank() 或者 Row_number()，而不是Dense_number()
使用最大优先队列（堆），poll() 第k次返回的即为第k大的数；
或者最小优先队列，poll()第n-k+1次即为第k大的数；
而使用数组，第k大的数，即nums数组中n-k索引的元素；

注意：Queue的方法，poll()会删除元素，peek()不会删除元素；

方法一：最大、最小优先队列

最大优先队列：
需要传入Comparator匿名内部类，重写compare方法；

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        PriorityQueue<Integer> p=new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o2-o1; //  若o1 o2反过来则是从大到小排列
            }
        });
        for(int i=0;i<n;i++){
            p.add(nums[i]);
        }
        int r=0;
        for(int j=0;j<k;j++ ){
            r=p.poll();
        }
        return r;
    }
}

最小优先队列：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        PriorityQueue<Integer> p=new PriorityQueue<>();
        for(int i=0;i<n;i++){
            p.add(nums[i]);
        }
        int r=0;
        for(int j=0;j<n-k+1;j++ ){
            r=p.poll();
        }
        return r;
    }
}

方法二：排序

冒泡：（超时）

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 冒泡
        for(int i=nums.length-1;i>0;i--){
            for(int j=0;j<i;j++){
                if(nums[j]>nums[j+1]){
                    int temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;
                }
            }
        }
        int n=nums.length;
        return nums[n-k];

    }
}

快排：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 快排
        sort(nums);
        int n=nums.length;
        return nums[n-k];
    }

    void sort(int[] nums ){
        int lo=0;
        int hi=nums.length-1;
        sort(nums,lo,hi);
    }

    void sort(int[] nums,int lo,int hi){
        if(lo>=hi){
            return;
        }
        // 前序
        int partition=partition(nums,lo,hi);
        sort(nums,lo,partition-1);
        sort(nums,partition+1,hi);
    }

    int partition(int[] nums,int lo,int hi){
        int key=nums[lo];
        int left=lo;
        int right=hi+1;
        while(true){
            while(nums[--right]>key){
                if(right<=lo){
                    break;
                }
            }
            while(nums[++left]<key){
                if(left>=hi){
                    break;
                }
            }
            if(left>=right){
                break;
            }else{
                swap(nums,left,right);
            }
        }
        swap(nums,lo,right);
        return right;
    }

    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}