首先我想到的是建一个hash表，存放每个数字对应的次数；但是题目没有给定数组的大小，这样做可能无限大；
然后先到可以对数组排序，这样遍历一次就可以了；但时间复杂度为O(nlog(n))
这里我们的思路是，遍历数组，记录一个数字和次数times；遇到相同的数字则次数加一，遇到不同的数字则减一；如果次数变为0，则数字更新为当前的数字，并把次数置1；如此遍历之后，因为我们要寻找的数字次数超过总数字一半，最后有一个数字的次数不为0，得到的就是我们要找到的数字。可以自己举例子体会一下。
这一段代码如下：
int ret = arr[0];
int n = 1;
for (int i =1 ; i < len; i++)
{
if (n == 0)
{
ret = arr[i];
n = 1;
}
else if (arr[i] == ret)
n++;
else
n--;
}
为了增加程度对错误输入的处理能力，加入了几行判断的语句：
bool inputInvalid = false;
int findNUmber(int* arr,int len)
{
int ret = arr[0];
int n = 1;
if (!arr || len == 0)
{
inputInvalid = true;
return 0;
}
for (int i =1 ; i < len; i++)
{
if (n == 0)
{
ret = arr[i];
n = 1;
}
else if (arr[i] == ret)
n++;
else
n--;
}
//check if input valid
n = 0;
for (int i = 0; i < len; i++)
{
if (arr[i] == ret)
n++;
}
if (n * 2 < len)
inputInvalid = true;
if (!inputInvalid)
return ret;
else
return 0;
}
