首先我想到的是建一個(gè)hash表，存放每個(gè)數(shù)字對(duì)應(yīng)的次數(shù)；但是題目沒有給定數(shù)組的大小，這樣做可能無(wú)限大；
然后先到可以對(duì)數(shù)組排序，這樣遍歷一次就可以了；但時(shí)間復(fù)雜度為O(nlog(n))

這里我們的思路是，遍歷數(shù)組，記錄一個(gè)數(shù)字和次數(shù)times；遇到相同的數(shù)字則次數(shù)加一，遇到不同的數(shù)字則減一；如果次數(shù)變?yōu)?，則數(shù)字更新為當(dāng)前的數(shù)字，并把次數(shù)置1；如此遍歷之后，因?yàn)槲覀円獙ふ业臄?shù)字次數(shù)超過總數(shù)字一半，最后有一個(gè)數(shù)字的次數(shù)不為0，得到的就是我們要找到的數(shù)字?？梢宰约号e例子體會(huì)一下。
這一段代碼如下：

    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--;

    }

為了增加程度對(duì)錯(cuò)誤輸入的處理能力，加入了幾行判斷的語(yǔ)句：

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;
}