题目：
Given an array of sizen, 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);}所以平均时间复杂度会有n*O(logn)，能AC。
但是总觉得有点不够，于是看了一下别人的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;
问候不一定要慎重其事，但一定要真诚感人
