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

导读:本篇文章讲解 LeetCode 215:数组中的第K个最大元素,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

链接

题目:
在这里插入图片描述

思路:

题目说不是第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;
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/89233.html

(0)
小半的头像小半

相关推荐

极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!