面试题29：数组中出现次数超过一半的数字

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

分析

• 最直观的解决办法就是将数组排序，然后取其中位数即可。但排序最快也需要O(nlgn)的时间复杂度，效率不是特别高。代码略。

• 还可以基于快速排序中的partition函数来求解。partition函数每次能确定一个值在数组中的确切位置。因此在找到位于数组中间位置的数字即可停止。 代码如下：

template<typename t="">
int Partition(vector<t>&amp; v,int left,int right)
{
    int i=left,j=right-1;
    T tmp=v[left];
    while(i<j)
    {
        while(i<j &amp;&amp; v[i]<=tmp)
            i++;
        swap(v[i],v[j]);
        while(i<j vj="">=tmp)
            j--;
        swap(v[i],v[j]);
    }
    return i;
}

template<typename t="">
T _MoreThanHalfNum(vector<t>&amp; v,int left,int right)throw (NoNumIsMoreThanHalf)
{
    int mid=Partition(v,left,right);
    if(mid==v.size()/2)
    {
        if(CheckNumIsMoreThanHalf(v,mid))
            return v[mid];
        else
            throw NoNumIsMoreThanHalf();
    }
    else if(mid<v.size()/2)
        return _MoreThanHalfNum(v,mid+1,right);
    else
        return _MoreThanHalfNum(v,left,mid);
}

template<typename t="">
T MoreThanHalfNum(vector<t>&amp; v)
{
    _MoreThanHalfNum(v,0,v.size());
}
</t></typename></t></typename></j></t></typename>```

*   最优的方法是设置两个数字num和time，num表示数组中的某一个数字，time代表num出现的次数。我们可以从前往后遍历数组，如果当前值等于num，就给time++；如果不等于，就time–；当time减少到0时，用下一个数字替换num的值。这样下来，只需要遍历一遍数组，就可以找出出现次数超过一半的数字。
代码如下：

template T MoreThanHalfNum(const vector& v) { if(v.size()==0) throw NoNumIsMoreThanHalf(); T num=v[0]; int time=1; int i; for(i=1;i0) { if(v[i]==num) { time++; } else { time--; } } else { num=v[i]; time=1; } } if(CheckNumIsMoreThanHalf(v,num)) return num; else throw NoNumIsMoreThanHalf(); } ```

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往