/**
 *	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.
 *	
 *	Challenge: O(n) time and O(1) extra space
 *
 *	Author: matao
 *
 */

import java.util.Arrays;

public class MajorityElement {
	public static int majorityElement(int[] nums) {
		Arrays.sort(nums);
		return nums[nums.length / 2];
    }

    public static void main(String[] args) {
    	int[] nums = {1, 1, 1, 1, 2, 2, 2};
    	System.out.println(majorityElement(nums));
    }
}
@@ -400,16 +400,17 @@
 yElement
+1
 (int%5B%5D n
@@ -476,16 +476,466 @@
 %0A    %7D%0A%0A
+    // %E6%AF%8F%E6%89%BE%E5%87%BA%E4%B8%A4%E4%B8%AA%E4%B8%8D%E5%90%8C%E7%9A%84element%EF%BC%8C%E5%B0%B1%E6%88%90%E5%AF%B9%E5%88%A0%E9%99%A4%E5%8D%B3count--%EF%BC%8C%E6%9C%80%E7%BB%88%E5%89%A9%E4%B8%8B%E7%9A%84%E4%B8%80%E5%AE%9A%E5%B0%B1%E6%98%AF%E6%89%80%E6%B1%82%E7%9A%84%E3%80%82%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%9AO(n)%0A    // Moore%E2%80%99s Voting Algorithm%0A    public static int majorityElement2(int%5B%5D nums) %7B%0A    %09int element = 0;%0A    %09int count = 0;%0A    %09for (int i = 0; i %3C nums.length; i++) %7B%0A    %09%09if (count == 0) %7B%0A    %09%09%09element = nums%5Bi%5D;%0A    %09%09%09count = 1;%0A    %09%09%7D else %7B%0A    %09%09%09if(element == nums%5Bi%5D) %7B%0A    %09%09%09%09count++;%0A    %09%09%09%7D else %7B%0A    %09%09%09%09count--;%0A    %09%09%09%7D%0A    %09%09%7D%0A    %09%7D%0A    %09return element;%0A    %7D%0A%0A
     publ
@@ -1051,16 +1051,66 @@
 yElement
+1(nums));%0A    %09System.out.println(majorityElement2
 (nums));

add new solution