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 输出。
时间复杂度：统计词频 O(n * m). 输出 freq >= k，最坏情况 O(n * m). 每个数字只出现了一次。Overall, O(n * m)
空间复杂度： O(n * m). 

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();

        }

    }

Read full article from Buttercola: Indeed: Find elements more than K times