算法test006

Top K问题。实现堆的，最小（或者最大）的10个数。
思路：（堆或快排）
最小Top K
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class test006 {
public static void main(String[] args) {
int[]arr=new int[]{1, 7, 2, 11, 5, 25, 8, 10, 9, 13, 15, 17, 23, 34, 45};
System.out.println(Arrays.toString(findKMin( arr,10)));
}
////要找前k个最小数，则构建大顶堆，要重写compare方法
public static int[] findKMin(int[] nums, int k) {

    PriorityQueue<Integer> pq =
            new PriorityQueue<>(k, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });

    for (int num : nums) {
        if (pq.size() < k) {
            pq.offer(num);
        } else if (pq.peek() > num) {//如果堆顶元素 > 新数，则删除堆顶，加入新数入堆
            pq.poll();
            pq.offer(num);
        }
    }

    int[] result = new int[k];
    for (int i = 0; i < k&&!pq.isEmpty(); i++) {
        result[i] = pq.poll();
    }
    return result;
}

}
/**
输出：[15, 13, 11, 10, 9, 8, 7, 5, 2, 1]
*/

最大Top K
import java.util.Arrays;
import java.util.PriorityQueue;

public class test006 {
public static void main(String[] args) {
int[]arr=new int[]{1, 7, 2, 11, 5, 25, 8, 10, 9, 13, 15, 17, 23, 34, 45};
System.out.println(Arrays.toString(findKMax( arr,10)));
}
//找出前k个最大数，采用小顶堆实现
public static int[] findKMax(int[] nums, int k) {
PriorityQueue<integer> pq = new PriorityQueue<>(k);//队列默认自然顺序排列，小顶堆，不必重写compare
for (int num : nums) {
if (pq.size() < k) {
pq.offer(num);
} else if (pq.peek() < num) {//如果堆顶元素 < 新数，则删除堆顶，加入新数入堆
pq.poll();
pq.offer(num);
}
}</integer>

    int[] result = new int[k];
    for (int i = 0; i < k&&!pq.isEmpty(); i++) {
        result[i] = pq.poll();
    }
    return result;
}

}
/**
输出：[9, 10, 11, 13, 15, 17, 23, 25, 34, 45]
*/
欢迎交流指正~