## Friday, February 19, 2016

### Indeed: Find elements more than K times

Buttercola: Indeed: Find elements more than K times
Given m sorted lists, find out the elements more than k times. If an element appear more than once in a list, count it only once.
Example:
1->2->2->4
2->3->4
3->3->4

k = 2

Output:
2 (appear twice)
3 (appear twice)
4 (appear 3 times)

Naive Solution:
Use a HashMap 做 词频统计，注意每一个list 相同的值只统计一次。最后再扫一遍Map, 对 大于等于 k 的elements 输出。

A space efficient solution:
Naive 的方法的问题在于如果n 很长（题目的假设），这样子空间的开销太大。有没有少用空间的方法？

Use a min-heap. 类似于merge k-sorted lists的方法。首先把每个list的第一个元素放入min PQ 中去。
`    ``List<Integer> findMoreThanKTimes(List<List<Integer>> lists, ``int` `k) {`
`        ``if` `(lists == ``null` `|| lists.size() == ``0``) {`
`            ``return` `null``;`
`        ``}`
`        `
`        ``List<Integer> result = ``new` `ArrayList<>();`
`        `
`        ``PriorityQueue<Node> minPQ = ``new` `PriorityQueue<>(``new` `MyNodeComparator());`
`        ``// step 1: put the first node of each list into the queue`
`        ``for` `(List<Integer> list : lists) {`
`            ``if` `(list != ``null`  `&& !list.isEmpty()) {`
`                ``minPQ.offer(``new` `Node(list.iterator()));`
`            ``}`
`        ``}`
`        `
`        ``while` `(!minPQ.isEmpty()) {`
`            ``Node curr = minPQ.poll();`
`            ``int` `currVal = curr.val;`
`            ``int` `count = ``1``;`
`            `
`            ``// put the next node into pq, skip the repeated element`
`            ``while` `(curr.iterator.hasNext()) {`
`                ``int` `nextVal = curr.iterator.next();`
`                ``if` `(currVal == nextVal) {`
`                    ``continue``;`
`                ``} ``else` `{`
`                    ``curr.val = nextVal;`
`                    ``minPQ.offer(curr);`
`                    ``break``;`
`                ``}`
`            ``}`
`            `
`            ``// get all repeated elements from the pq`
`            ``while` `(!minPQ.isEmpty() && currVal == minPQ.peek().val) {`
`                ``count++;`
`                ``Node node = minPQ.poll();`
`                ``int` `nodeVal = node.val;`
`                `
`                ``// put the next node into pq, skip the repeated elements`
`                ``while` `(node.iterator.hasNext()) {`
`                    ``int` `nextNodeVal = node.iterator.next();`
`                    ``if` `(nodeVal == nextNodeVal) {`
`                        ``continue``;`
`                    ``} ``else` `{`
`                        ``node.val = nextNodeVal;`
`                        ``minPQ.offer(node);`
`                        ``break``;`
`                    ``}`
`                ``}`
`            ``}`
`            `
`            ``if` `(count >= k) {`
`                ``result.add(currVal);`
`            ``}`
`        ``}`
`        `
`        ``return` `result;`
`    ``}`
`    `
`    ``class` `MyNodeComparator ``implements` `Comparator<Node>{`
`        ``@Override`
`        ``public` `int` `compare(Node a, Node b) {`
`            ``return` `a.val - b.val;`
`        ``}`
`    ``}`
`    `
`    ``class` `Node {`
`        ``int` `val;`
`        ``Iterator<Integer> iterator;`
`        `
`        ``public` `Node(Iterator<Integer> iterator) {`
`            ``this``.iterator = iterator;`
`            ``val = iterator.next();`
`        ``}`
`    ``}`