[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].

Java 程式碼

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
       if(A.length == 0)
         return -1;
         
       int count = 0;
       int lastNum = A[0];
       
       Arrays.sort(A);
       for(int i = 0; i < A.length; i++){
           if(count == 0){
               count++;
               lastNum = A[i];
           }else{
                if(A[i] == lastNum){
                    count ++;
                }else{
                   count--;
                }
                
           }
          
       } 
       
       int index = -1;
       int ct = 0;
       for(int i = 0;i < A.length;i++){
           if(A[i] == lastNum){
              index = i;
              ct++;
           }
           
       }
       if(ct > A.length/2){
         return index;
        }
        return -1;
    }
}

分數共拿 91%，仍然有一個測試資料過不了，
但是 Codility 又沒有明說是丟甚麼資料，故待釐清問題點。
結果拔掉 Arrays.sort(A) 就滿分了，神奇。

任何問題歡迎交流討論，一起學習！

更多面試相關

⇒ [Codility] 面試寫題目經驗感想



感謝相關連結
https://www.codility.com/
https://app.codility.com/programmers/lessons/8-leader/