Programming: Majority Element in List

If you're new here, you may want to subscribe to my RSS feed. Thanks for visiting!

Q: In a list, a majority element is defined as an element that occurs more than n/2 times. Given an input list, how can you determine the majority element, if present?
A:

We will use a lookup table to store a count of how many times each element occurs. Once we create this table, we can use the lookup table to determine if any element has a corresponding count of more than (n/2 + 1).

	/**
	 * Returns the index of the majority element.
	 * If no majority element is present, then -1 is returned
	 * @param input
	 * @return
	 */
	public static int majorityElement(int[] input){
		Map lookup = new HashMap();
		for(int i = 0; i < input.length; i++){
			Integer temp = lookup.get(input[i]);
			if (temp == null) temp = 1;
			else temp++;
			lookup.put(input[i], temp);
		}

		for(int i = 0; i < input.length; i++){
			int count = lookup.get(input[i]);
			if (count >= input.length/2 + 1) return i;
		}
		return -1;
	}