データ構造の面接問題のまとめ2——配列:出現回数が半分を超える要素を求めます.

この問題に遭遇する一番簡単な考えは、各要素の出現回数を統計することです.しかし、配列の中にいくつの要素があるかは分かりません.他の記憶空間を使って、結果を検索する時も、結果の行列を巡回する必要があります.
正しい解決方法は重複要素(結果要素)の数を記録し、異なる要素に出会うとマイナス(相殺に相当)になり、結果要素に出会うのも同じです.
考えてみると、結果の要素は半分以上になりますので、すべての要素が相殺されたら、必ず結果の要素が残ります.
この方法は一次配列のみを巡回した.

int FindNum(int *a, int n)
{
	int result = a[0];
	int result_count = 1;
	for (int i = 1; i < n; i++)
	{
		if (a[i]==result)
		{
			result_count++;
		} 
		else
		{
			result_count--;
			if (result_count==0)
			{
				result = a[i];
				result_count = 1;
			}
		}
	}
	return result;
}