整数数组中寻找第K大元素

楚天乐 103 0 条

算法思想

使用最大堆结构,最大堆的顶部总是最大元素。因此我们只需要构建一个最大堆,然后循环取K次堆顶就可以拿到目标元素。

堆是什么,怎么使用堆,这里不做讨论。

算法复杂度分析

  • 构建堆:O(N)
  • 取出K个元素,K常数,算法复杂度O(N)

上代码

import java.util.*;

public class Finder {
    PriorityQueue<Integer> maxHeap;

    public int findKth(int[] a, int n, int K) {
        // write code here
        createHeap(a, n);
        int val = 0;
        for(int i=0; i<K; i++){
            val = maxHeap.poll();
        }
        return val;
    }

    public void createHeap(int[] a, int n){
        maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return - Integer.compare(o1, o2);
            }
        });

        // add to the max heap
        for(int i=0; i<n; i++){
            maxHeap.offer(a[i]);
        }
    }
}

优化

取出K个元素,在K<1/2n时候,最大堆适用。如果K大于1/2*n, 用最小堆更划算。取元素次数可以保证小于1/2n

这个优化没啥难度,我就不写了

打赏

微信打赏

支付宝打赏



发表我的评论
昵称 (必填)
邮箱 (必填)
网址
执行时间: 52.551984786987 毫秒