leetcode 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 int majorityElement(int[] num) {
		Arrays.sort(num,0,num.length);
		return num[num.length/2];
}

不过可以看一下java的源码，Arrays的sort方法用的是快排：

public static void sort(int[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
}

但是总觉得有点不够，于是看了一下别人的solution。

方法二：

时间复杂度O(n)

用一个计数器counter记数，用一个变量candidate存储候选值，遍历数组，如果当前值和前一个值相同，counter+1，如果不同，counter-1，如果counter==0了，candidate移动到当前元素。设想极度乱序的情况，那个元素被尽可能多的隔开了，但是至少有一组一定是两个以上连续的那个元素，所以最后的candidate就是我们需要的值。

<span style="white-space:pre">	</span>int candidate = 0;
        int counter = 0;
        for(int i=0;i<num.length;i++)
        {
        	if(counter==0)
        	{
        		candidate = num[i];
        		counter++;
        	}
        	else{
        		if(num[i]==candidate)counter++;
        		else counter--;
        	}
        }
<span style="white-space:pre">	</span>return candidate;

leetcode majority element

原文：http://blog.csdn.net/gotobar/article/details/43819625