[Codility] Dominator

  An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

 

  A에 포함되는 원소들에 대해 Count를 해야하기 때문에 HashMap 구조를 이용하였다. HashMap의 put, get, containsKey 은 O(1), worst O(n) 이기때문에 유용하다. (* containsValue = O(n) )

 

import java.util.*;

class Solution {
    public int solution(int[] A) {
        
        HashMap<Integer, Integer> cnt = new HashMap<>();
        
        int half = A.length;
        half /= 2;
        
        if(A.length == 1){
            return 0;
        }
        
        for(int i = 0; i < A.length; i++){
            if(cnt.containsKey(A[i])){
                cnt.put(A[i], cnt.get(A[i])+1);
                if(cnt.get(A[i]) > half){
                    return i;
                }
            }
            else{
                cnt.put(A[i], 1);
            }
        }
        return -1;
    }
}