Monday, February 15, 2016

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 中去。


Code (Java):
import java.util.*;

public class Solution {
    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;
        }
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        Integer[] b = new Integer[]{1, 2, 2, 4};
        Integer[] a = new Integer[]{2, 3, 4};
        Integer[] c = new Integer[]{3, 3, 4};
        
        List<List<Integer>> lists = new ArrayList<>();
        lists.add(Arrays.asList(a));
        lists.add(Arrays.asList(b));
        lists.add(Arrays.asList(c));
        
        List<Integer> result = sol.findMoreThanKTimes(lists, 2);
        
        for (Integer e : result) {
            System.out.print(e + " ");
        }
        
        System.out.println(" ");
    }
    
    class Node {
        int val;
        Iterator<Integer> iterator;
        
        public Node(Iterator<Integer> iterator) {
            this.iterator = iterator;
            val = iterator.next();
        }
    }
}

No comments:

Post a Comment