Top K 最大值(最小值)问题

Top K问题指的是从大量数据中获取前K个最大值或者最小值。 我们可以用miniHeap解决TopK最大值问题,或者MaxHeap解决TopK最小值问题, 时间复杂度O(nlogK)。

最小堆解决TopK最大值的解决方法就是:先去源数据中的K个元素放到一个长度为K的数组中去,再把数组转换成最小堆。再依次取源数据中的K个之后的数据和堆的根节点(数组的第一个元素)比较,根据最小堆的性质,根节点一定是堆中最小的元素,如果小于它,则直接pass,大于的话,就替换掉跟元素,并对根元素进行Heapify,直到源数据遍历结束。堆中元素就是TopK的最大元素。

Java 中实现Priority Queue.

 maxPQ = new PriorityQueue<Integer>();
 miniPQ = new PriorityQueue<Integer>(new Comparator<Integer>(){
        public int compare(Integer i1, Integer i2) {
            return i2 - i1;
        }
 });

Reference:
http://blog.csdn.net/xiao__gui/article/details/8687982
http://baozitraining.org/blog/mitbbs-google-k-largest-elements/

Advertisements

252/253. Meeting Rooms I/II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei),
1. determine if a person could attend all meetings.
2.find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
1. determine if a person could attend all meetings.
思路: 求是否能参加所有的会议。 也就是找一个会议的start跟其他会议的end是否有冲突.
复杂度: time:O(nlogn),space:O(1)

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0)
            return true;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });    
        int end = intervals[0].end;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < end) { // 会议开始时间小于最晚结束时间
                return false;
            }
            end = Math.max(end, intervals[i].end);
        }
        return true;
    }
}

2.find the minimum number of conference rooms required.
思路: 求总共需要多少个会议室, 贪心的思路,这里的trick是借助mini heap,同样存每个会议的结束时间,heap中总是返回最早结束的会议。我们遍历会议的时候,找当前会议的start跟heap中最早的结束的会议的end进行比较,也就是当mtg2.start )heap.peek(也就是最早结束meeting的end), 那么我们可以把当前meeting安排到这个房间,这时把heap.poll(),存入当前meeting的end。 否则的话,开辟一个新的房间来放,也就是直接把当前meeting的end放入heap。 最后返回heap.size 就是需要的房间.
复杂度: time O(nlogn), space O(1)

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0)
            return 0;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval v1, Interval v2) {
                return v1.start - v2.start;
            }
        });    
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(intervals[0].end);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start >= heap.peek()) {// 下一个meeting的start晚与或者等于上一个meeting的end.
                heap.poll();
            }
            heap.add(intervals[i].end);
        }
        return heap.size();
    }
}