Majority Number III

Medium Majority Number III

24%

Accepted

Given an array of integers and a number k, the majority number is the number that occursmore 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

ublic class Solution {

    /**

     * @param nums: A list of integers

     * @param k: As described

     * @return: The majority number

     */

    public int majorityNumber(ArrayList<Integer> nums, int k) {

        // write your code

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        

        for(int num : nums){

            if(map.size() < k && !map.containsKey(num)){

                map.put(num, 1);

            } else if(map.containsKey(num)){

                map.put(num, map.get(num)+1);

            } else{

                Map<Integer, Integer> temp = new HashMap<Integer, Integer>();

                for(int key : map.keySet()){

                    if(map.get(key) > 1){

                        temp.put(key, map.get(key)-1);

                    }

                }

                map = temp;

            }

        }

        int c = 0;

        int res = 0;

        for(int key : map.keySet()){

            if(map.get(key) > c){

                c = map.get(key);

                res = key;

            }

        }

        return res;

    }

}