package leetcode.easy;

import java.util.Arrays;

import java.util.HashMap;

import java.util.Map;

import java.util.Random;

public class MajorityElement {

	@org.junit.Test

	public void test() {

		int[] nums1 = { 3, 2, 3 };

		int[] nums2 = { 2, 2, 1, 1, 1, 2, 2 };

		System.out.println(majorityElement1(nums1));

		System.out.println(majorityElement1(nums2));

		System.out.println(majorityElement2(nums1));

		System.out.println(majorityElement2(nums2));

		System.out.println(majorityElement3(nums1));

		System.out.println(majorityElement3(nums2));

		System.out.println(majorityElement4(nums1));

		System.out.println(majorityElement4(nums2));

		System.out.println(majorityElement5(nums1));

		System.out.println(majorityElement5(nums2));

		System.out.println(majorityElement6(nums1));

		System.out.println(majorityElement6(nums2));

	}

	public int majorityElement1(int[] nums) {

		int majorityCount = nums.length / 2;

		for (int num : nums) {

			int count = 0;

			for (int elem : nums) {

				if (elem == num) {

					count += 1;

				}

			}

			if (count > majorityCount) {

				return num;

			}

		}

		return -1;

	}

	private Map<Integer, Integer> countNums(int[] nums) {

		Map<Integer, Integer> counts = new HashMap<Integer, Integer>();

		for (int num : nums) {

			if (!counts.containsKey(num)) {

				counts.put(num, 1);

			} else {

				counts.put(num, counts.get(num) + 1);

			}

		}

		return counts;

	}

	public int majorityElement2(int[] nums) {

		Map<Integer, Integer> counts = countNums(nums);

		Map.Entry<Integer, Integer> majorityEntry = null;

		for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {

			if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {

				majorityEntry = entry;

			}

		}

		return majorityEntry.getKey();

	}

	public int majorityElement3(int[] nums) {

		Arrays.sort(nums);

		return nums[nums.length / 2];

	}

	private int randRange(Random rand, int min, int max) {

		return rand.nextInt(max - min) + min;

	}

	private int countOccurences(int[] nums, int num) {

		int count = 0;

		for (int i = 0; i < nums.length; i++) {

			if (nums[i] == num) {

				count++;

			}

		}

		return count;

	}

	public int majorityElement4(int[] nums) {

		Random rand = new Random();

		int majorityCount = nums.length / 2;

		while (true) {

			int candidate = nums[randRange(rand, 0, nums.length)];

			if (countOccurences(nums, candidate) > majorityCount) {

				return candidate;

			}

		}

	}

	private int countInRange(int[] nums, int num, int lo, int hi) {

		int count = 0;

		for (int i = lo; i <= hi; i++) {

			if (nums[i] == num) {

				count++;

			}

		}

		return count;

	}

	private int majorityElementRec(int[] nums, int lo, int hi) {

		// base case; the only element in an array of size 1 is the majority

		// element.

		if (lo == hi) {

			return nums[lo];

		}

		// recurse on left and right halves of this slice.

		int mid = (hi - lo) / 2 + lo;

		int left = majorityElementRec(nums, lo, mid);

		int right = majorityElementRec(nums, mid + 1, hi);

		// if the two halves agree on the majority element, return it.

		if (left == right) {

			return left;

		}

		// otherwise, count each element and return the "winner".

		int leftCount = countInRange(nums, left, lo, hi);

		int rightCount = countInRange(nums, right, lo, hi);

		return leftCount > rightCount ? left : right;

	}

	public int majorityElement5(int[] nums) {

		return majorityElementRec(nums, 0, nums.length - 1);

	}

	public int majorityElement6(int[] nums) {

		int count = 0;

		Integer candidate = null;

		for (int num : nums) {

			if (count == 0) {

				candidate = num;

			}

			count += (num == candidate) ? 1 : -1;

		}

		return candidate;

	}

}