Lesson 6: Dominator (Dominator)

Lesson 6: Dominatorhttps://codility.com/programmers/lessons/6

この解答も同じようにCodilityの解説するleaderを見つけるアルゴリズムを使用していますので、まず読んでみてください。
Open reading material (PDF)

そして、実際にはこの問題でいうdominatorは定義をみるとleaderと同じものですね。一つ前の問題の解答も気になれば見てみてください。
(http://codility-lessons.blogspot.tw/2015/02/lesson-6-equileader.html)

dominator(leader)をまず見つけて、存在すれば再度配列をスキャンして最初に発見したインデックスを返してみましょう。

これで１００％のスコアがもらえます。

#include <alloca.h>

int solution(int A[], int N) {
    
    //first find the leader and count its occurances.
    //as all the values on the stack will be the same,
    //we only have to keep one value.
    int sp = 0;
    int candidate = 0;
    
    int i;
    for (i = 0; i < N; i++){
        if (sp == 0){
            sp++;
            candidate = A[i];
            continue;
        }
        
        if (candidate == A[i]){
            sp++;
        }
        else {
            sp--;
        }
    }
    
    //if there is no dominator, return -1
    if (sp == 0){
        return -1;
    }
    
    //now we check if the candidate value is really a dominator
    int cnt = 0;
    for (i = 0; i < N; i++){
        if (A[i] == candidate){
            cnt++;
        }
    }
    
    //if there is no dominator, return -1.
    if (cnt <= N / 2){
        return -1;
    }
    
    //now we have a leader.
    int dominator = candidate;
  
    
    //let's find the first dominator in the array
    for (i = 0; i < N; i++){
        if (A[i] == dominator){
            return i;
        }
    }
    
    //the code won't reach here since we have a dominator. 
    return -1;
}

しかし！dominatorのインデックスであれば何を返しても良いということになっているので、配列をスキャンする必要はないですね。単に、最後に見つかったインデックスを保存しておき、それを返しましょう。これでも100%のスコアがとれます。

#include <alloca.h>

int solution(int A[], int N) {

    

    //first find the leader and count its occurances.

    //as all the values on the stack will be the same,

    //we only have to keep one value.

    int sp = 0;

    int candidate = 0;

    int lastIndex = 0;

    

    int i;

    for (i = 0; i < N; i++){

        if (sp == 0){

            sp++;

            candidate = A[i];

            lastIndex = i;

            continue;

        }

        

        if (candidate == A[i]){

            sp++;

            lastIndex = i;

        }

        else {

            sp--;

        }

    }

    

    //if there is no dominator, return -1

    if (sp == 0){

        return -1;

    }

    

    //now we check if the candidate value is really a dominator

    int cnt = 0;

    for (i = 0; i < N; i++){

        if (A[i] == candidate){

            cnt++;

        }

    }

    

    if (cnt > N / 2){

        return lastIndex;

    }

    

    //if there is no dominator, return -1

    return -1;

}