Lintcode: Majority Number III

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

Find it.

Have you met this question in a real interview? Yes
Example
Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.

Note
There is only one majority number in the array.

Challenge
O(n) time and O(k) extra space

这道题跟Lintcode: Majority Number II思路很像，那个找大于1/3的，最多有两个candidate，这个一样，找大于1/k的，最多有k-1个candidate

维护k-1个candidate 在map里面，key为数字值，value为出现次数。先找到这k-1个candidate后，扫描所有元素，如果该元素存在在map里面，update map；如果不存在，1：如果map里面有值为count= 0，那么删除掉这个元素，加入新元素；2：map里面没有0出现，那么就每个元素的count--

注意：有可能map里有多个元素count都变成了0，只用删掉一个就好了。因为还有0存在，所以下一次再需要添加新元素的时候不会执行所有元素count-1, 而是会用新元素替代那个为0的元素

这道题因为要用map的value寻找key，所以还可以用map.entrySet(), return Map.Entry type, 可以调用getKey() 和 getValue()

 1 public class Solution {
 2     /**
 3      * @param nums: A list of integers
 4      * @param k: As described
 5      * @return: The majority number
 6      */
 7     public int majorityNumber(ArrayList<Integer> nums, int k) {
 8         // write your code
 9         if (nums==null || nums.size()==0 || k<=0) return Integer.MIN_VALUE;
10         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
11         int i = 0;
12         for (; i<nums.size(); i++) {
13             int key = nums.get(i);
14             if (map.containsKey(key)) {
15                 map.put(key, map.get(key)+1);
16             }
17             else {
18                 map.put(key, 1);
19                 if (map.size() >= k) break;
20             }
21         }
22         while (i < nums.size()) {
23             int key = nums.get(i);
24             if (map.containsKey(key)) {
25                 map.put(key, map.get(key)+1);
26             }
27             else {
28                 if (map.values().contains(0)) { //map contains value 0
29                     map.put(key, 1); // add new element to map
30                     //delete key that has value 0
31                     int zeroKey = 0;
32                     for (int entry : map.keySet()) {
33                         if (map.get(entry) == 0) {
34                             zeroKey = entry;
35                             break;
36                         }
37                     }
38                     map.remove(zeroKey);
39                 }
40                 else {
41                     for (int nonzeroKey : map.keySet()) {
42                         map.put(nonzeroKey, map.get(nonzeroKey)-1);
43                     }
44                 }
45             }
46             i++;
47         }
48         
49         HashMap<Integer, Integer> newmap = new HashMap<Integer, Integer>();
50         int max = 0;
51         int major = 0;
52         for (int j=0; j<nums.size(); j++) {
53             int cur = nums.get(j);
54             if (!map.containsKey(cur)) continue;
55             if (newmap.containsKey(cur)) {
56                 newmap.put(cur, newmap.get(cur)+1);
57             }
58             else {
59                 newmap.put(cur, 1);
60             }
61             if (newmap.get(cur) > max) {
62                 major = cur;
63                 max = newmap.get(cur);   
64             }
65         }
66         return major;
67     }
68 }