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

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


分析

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上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")