Lesson 8 - 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].

---

내 답안

map key value로 값을 저장해놓고 구하였다.
Collections Class에서 max값을 뽑아 내는데 kotlin 만써서 할지 몰라 애를 먹었다.

import java.util.Map;
import java.util.HashMap;
import java.util.Collections;
import java.util.Comparator;
class Solution {
    public int solution(int[] A) {
        Map map = new HashMap();

        if (A.length == 0) {
            return -1;
        }

        if (A.length == 1) {
            return 0;
        }

        for(int n: A) {
            int number = 0;
            if (map.get(n) != null) {
                number = (int) map.get(n);
            } 
            map.put(n, (number + 1));
        }

        int dominatorKey = (int) Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();
        int dominatorValue = (int) Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getValue();

        int resultIndex = 0;
        for(int i=0; i<A.length; i++) {
            if (A[i] == dominatorKey) {
                resultIndex = i;
                break;
            }
        }
        
        return dominatorValue > (double) A.length/2.0 ? resultIndex : -1;
    }
}

---

좋은 답안

구글 검색해서 나온 곳의 답안인데 정렬을 하면 많이 count 되는 숫자가 중앙에 온다는 답이다. 비슷한 유형의 문제는 이렇게 풀어야 한다는 것을 알았다.

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        if( A.length == 0 ) return -1;

        int[] B = Arrays.copyOf(A, A.length);
        double half = A.length / 2.0;

        Arrays.sort(B);
        int candidate = B[(int)half];

        int count = 0;
        for( int i:B ){
            if( i > candidate ){
                break;
            }

            if( i == candidate ) count++;
        }

        int answer = -1;
        if( count > half ){
            for( int i=0; i<A.length; i++ ){
                if( A[i] == candidate){
                    answer = i;
                    break;
                }
            }
        }

        return answer;
    }
}