题目链接：majority-element

/**

 *

		Given an array of size n, find the majority element.

		The majority element is the element that appears more than ⌊ n/2 ⌋ times.

		You may assume that the array is non-empty and the majority element always exist in the array.

 *

 */

public class MajorityElement {

//	40 / 40 test cases passed.

//	Status: Accepted

//	Runtime: 253 ms

//	Submitted: 1 minute ago

	//时间复杂度为 O(n), 空间复杂度为 O(1)

	//因为最多的那个元素占一半及以上， 故能够和别的元素相互抵消，最后剩下的未抵消掉的元素为所求

	//将数组分成三块：num[0...i]为 归并的 还未抵消的数组。 num[i+1...j－1]空暇区， num[j...num.length-1]为等待抵消的数组

	//抵消规则：若num[i] = num[j] 则把num[j]归入num[0...i+1]数组中

	//		 若num[i] != num[j] 则把num[i] 抵消掉 然后 i－－

    static int majorityElement(int[] num) {

    	int i = -1;

    	for (int j = 0; j < num.length; j++) {

    		if(i == -1) num[++i] = num[j];

        	else {

            	if(num[j] == num[i]) num[ ++i] = num[j];

    			else i --;

			}

		}

    	return num[0];

    }

	public static void main(String[] args) {

		System.out.println(majorityElement(new int[]{4}));

		System.out.println(majorityElement(new int[]{4, 4, 5}));

		System.out.println(majorityElement(new int[]{4, 3, 3}));

		System.out.println(majorityElement(new int[]{4, 3, 4}));

	}

}