有一个int型数组长度为n，其中某个元素个数占绝大多数，即大于n/2，如何在O(n)复杂度内找到这个元素。

即：

输入{1,1,2}输出1

输入{4,4,1,2,1,2,4}输出4

思路：

遍历数组，对元素进行记数，可以当作军队攻山头的游戏， 每种元素视为一个军队， 上来一个本元素的士兵记数+1，来一个其他元素的士兵计数-1， 因为目标元素占绝大多数，一定是最后的胜利者， 计数为0时说明势均力敌，计数为-1时，新来的元素占上风，记录元素和计数

java代码：

static int findMajority(int[] arr){
		int num = 0;  // 山头小旗
		int count = 0;// 山头士兵数
		for(int e : arr){
				if(e == num){
						count ++; // 来了同军队的士兵，增加计数
				} else {
						count --; // 来了其他军队的士兵，减少计数
						if(count < 0){ // 当前元素占了上风
								num = e;  // 插上红旗
								count ++; // 增加计数
						}
				}
		}
		return num;
}

public static void main(String[] args) {
		int[] arr = {3,3,3,3,3,4,5,2,2};
		System.out.println(findMajority(arr));
}

输出：

3