Saturday, April 18, 2015

Leader - Dominator

Here is another codility problem solution from the codility lessons (Dominator-Find an index of an array such that its value occurs at more than half of indices in the array.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.




// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	public int solution(int[] A) {
		Integer[] equi = findEquiLeader(A);
		if (equi == null) return -1;
		else {
			int equiLeader = equi[0];
			int value = equi[1];
			return value;
		}
	}
	private Integer[] findEquiLeader(int[] A) {
		int len = A.length;
		int size = 0;
		Integer value = null;
		for (int i = 0; i < A.length; i++) {
			if (size == 0) {
				value = A[i];
				size++;
			} else {
				if (value == A[i]) {
					size++;
				} else {
					size--;
				}
			}
		}
		if (size > 0) {
			int count = 0;
			int index = 0;
			for (int i = 0; i < A.length; i++) {
				if (A[i] == value) {
					count++;
					index = i;
				}
			}
			if (count > A.length / 2) {
				return new Integer[] {
					value, index
				};
			}


		}
		return null;

	}
}

No comments:

Post a Comment