JAvaの配列に現れる回数が半分を超える数字

テーマ:配列の中に1つの数字が現れる回数が配列の長さの半分を超えているので、この数字を見つけてください.例えば、長さ9の配列{1,2,3,2,2,5,4,2}を入力します.数字2は配列中に5回出現し、配列長の半分を超えるため、出力2.
分析:2つの解法があります.
1.高速ソートにおけるpartition関数に基づくO(n)アルゴリズム.この配列を並べ替えると、並べ替えた配列の真ん中の数字は、配列の長さの半分を超える出現回数の数字に違いない.
2.配列特性に基づいて、配列を巡るときに2つの値を保存することが考えられます.1つは配列の中の数字で、1つはこの数字が現れる回数です.私たちが次の数字を遍歴するとき、次の数字が以前に保存した数字と同じであれば、回数は1を加え、そうでなければ回数は1を減らします.回数が0の場合、次の数字を保存し、回数を1に設定する必要があります.
JAvaコード:

package LinkList;

public class MoreThenHalfNumMain {
	boolean g_bInputInvalid = false;
//     partition   O(n)  
	public int MoreThenHalfNum1(int[] num, int length) {
		if (CheckInvalidArray(num, length))
			return 0;
		int middle = length >> 1;
		int start = 0;
		int end = length - 1;
		int index = Partition(num, start, end);
		while (index != middle) {
			if (index > middle) {
				end = index - 1;
				index = Partition(num, start, end);
			} else {
				start = index + 1;
				index = Partition(num, start, end);
			}

		}
		int result = num[middle];
		if (!CheckMoreThenHalf(num, length, result))
			return 0;
		return result;
	}
//            O(n)   
	public int MoreThenHalfNum(int[] num, int length) {
		if (CheckInvalidArray(num, length))
			return 0;
		int result = num[0];
		int times = 1;
		for (int i = 1; i < length; i++) {

			if (times == 0) {
				result = num[i];
				times = 1;

			} else if (num[i] == result) {
				times++;

			} else
				times--;

		}

		if (!CheckMoreThenHalf(num, length, result))
			return 0;
		return result;

	}

	private boolean CheckMoreThenHalf(int[] num, int length, int result) {
		int times = 0;
		for (int i = 0; i < length; i++) {
			if (num[i] == result)
				times++;

		}
		boolean isMoreThenHalf = true;
		if (times * 2 <= length) {
			g_bInputInvalid = true;
			isMoreThenHalf = false;

		}

		return isMoreThenHalf;
	}

	private int Partition(int[] a, int p, int q) {
		int x, i, j, temp;

		x = a[p]; //          x 
		i = p; //       i         
		for (j = p + 1; j <= q; j++) {
			if (a[j] <= x) //    x   ，     
			{
				i += 1;
				temp = a[i]; // exchange
				a[i] = a[j];
				a[j] = temp;
			}

		}

		temp = a[i]; // exchange
		a[i] = a[p];
		a[p] = temp;

		return i;

	}

	private boolean CheckInvalidArray(int[] num, int length) {
		g_bInputInvalid = false;
		if (num == null || length <= 0)
			g_bInputInvalid = true;
		return g_bInputInvalid;
	}

	public static void main(String[] args) {
		int a[] = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
		MoreThenHalfNumMain moreThenHalfNumMain = new MoreThenHalfNumMain();
		System.out.println(moreThenHalfNumMain.MoreThenHalfNum1(a, a.length));
        System.out.println(moreThenHalfNumMain.MoreThenHalfNum(a, a.length));
	}

}