数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

看到这个题目，我自己想到的方法：

另外申请一个数组B，用来存放该数组A 元素出现的次数，再遍历B数组，出现次数最多的就是；但是这个如果A数组当中的元素有个是1000，那么B数组就要申请至少1000，空间浪费太严重。

方法二：

类似于消除原理，既然某个数字大于长度的一半，那么我们就遍历数组，如果两个数不相等则消除，最后剩下的数就是我们要的。当然如果不存在这样的数，这是不行的。所以最后要再遍历一遍验证这个数的出现次数是否大于数组的一半。

我们在遍历数组的时候保存两个值，一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减掉1.如果次数为0，则我们要保存下一个数字，并把次数设为1

例如 1 2 3 2 2 2 5 4 2

遍历 1  值result = 1， 次数count = 1；遍历2， 1 ！= 2， count = 1-1=0； 遍历3 result = 3, conut = 1; ,。。。。。。。依次类推

// MoreThanHalfNum.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>using namespace std;bool g_InputInvalid = true;bool CheckInvalidArray(int array[],int nLength){	g_InputInvalid = false;	if (array == NULL || nLength <= 0)	{		g_InputInvalid = true;	}	return g_InputInvalid;}bool CheckMoreThanHalf(int array[], int nLength, int result){	int count = 0;	for (int i = 0; i < nLength; ++i)	{		if (result == array[i])		{			++count;		}	}	bool isMoreThanHalf = true;	if (count * 2 <= nLength)	{		g_InputInvalid = true;		isMoreThanHalf = false;	}	return isMoreThanHalf;}void FindKey(int array[], int nLength){	//判断数组是否有效	if (CheckInvalidArray(array,nLength))	{		return;	}	int result = array[0];	int count = 1;	for (int i = 1; i < nLength; ++i)	{		if (count == 0)		{			result = array[i];			count = 1;		}		else		{			if (result == array[i])			{				++count;			}			else			{				--count;			}		}	}	//判断数组是否符合标准，排除输入的数组的当中没有超过数组一半的情况	if (CheckMoreThanHalf(array,nLength,result) == 0)	{		result = 0;	}	if (result == 0)	{		cout<<"您的数组当中没有出现次数超过一半的数字"<<endl;	}	else	{		cout<<"您的数组当中出现次数超过一半的数字是："<<result<<endl;	}}int _tmain(int argc, _TCHAR* argv[]){	int array[9] = {1,2,3,2,8,2,2,9,2};	FindKey(array,9);	getchar();	return 0;}

注意要考虑如果不存在大于数组一半长度的情况！

方法三：

先进行排序，然后排序后中间的那个数字肯定就是我们要找的数字；

但是一般的排序算法都要 O(n*lgn); 我自己想到的那个方法时间复杂度为O(n)，但是空间牺牲太大；

总之两个方法都不是很好

最好的选择就是第二种方法！