Rafal's Blog - Codility Dominator – Majority Vote
Given an array A of N integers, a dominator of A is the element that appears more than half of the time. Given an array of integers A, find its dominator and return any index of the dominator, or return −1 if no dominator exists.
Given an array A of N integers, a dominator of A is the element that appears more than half of the time. Given an array of integers A, find its dominator and return any index of the dominator, or return −1 if no dominator exists.
def solution(A):
A_len = len(A)
candidate = -1
candidate_count = 0
candidate_index = -1
for index in xrange(A_len):
if candidate_count == 0:
candidate = A[index]
candidate_index = index
candidate_count += 1
else:
if A[index] == candidate:
candidate_count += 1
else:
candidate_count -= 1
if len([number for number in A if number == candidate]) <= A_len//2:
return -1
else:
return candidate_index
public static int dominator(int[] A) {
if(A.length == 0) return -1;
int count = 0;
int elem = A[0];
for(int i : A){
if(i == elem){
count++;
} else {
if(count == 0){
count++;
elem = i;
}
else count--;
}
}
int ct = 0;
int ind = -1;
for(int i = 0; i < A.length; i++){
if(A[i] == elem){
ct++;
ind = i;
}
}
if(ct > A.length/2) return ind;
else return -1;
}
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;
}
Read full article from Rafal's Blog - Codility Dominator – Majority Vote