整数配列があり、1つの数が半分を超えることが知られています.O(n)の複雑さのアルゴリズムでこの数を見つけてください.

package com.interview.sym;

public class TestCountest {

	/**
	 * @param args
	 *   ：         ，               ，  O(n)            。
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int candidate = 1 << 31;
		int vote = 0;
		int arr[] = { 1, 2, 3, 1, 2, 1,2, 1, 1, 5,2, 6 ,2,2,2,2};//              vote  

		for (int i = 0; i < arr.length; i++) {
			if (arr[i] != candidate) {
				if (vote == 0) {
					candidate = arr[i];
				} else {
					vote--;
				}

			} else {
				vote++;
			}
		}
		System.out.print(candidate );
	}

}
/*  ：  ：                ，      candidate vote，          ，    

             ：

 

          ，         1

           ,        1，         0，       ，           

 

                    。

 

        ：    ，            ，           ，             ，

               ，      ，          0，    。           

    。
*/