总体来说就是在一堆的数中，有某个数出现的次数超过了总数的一半或者1/3，1/4。

方法一

先排序，然后，遍历一遍找就行了。
但是面试中不是最终方法。

方法二

既然超过了一半，那么我们就每次从数组中删除两个不同的数，最后剩下的一定都是一样的了。
编程之美数上的代码，并不是真正意义上的删除，而是跳过两个不同的数。

int findTarget(vector<int> source)
{
    int target ;
    int counts=0;
    for(int i = 0;i<source.size();i++)
    {
        if(counts ==0)
        {
            target = source[i];
        }else{
            if(target  == source[i])
            {
                counts++;
            }else{
                counts--;
            }
        }
    }
    return counts;
}

代码解释

当counts==0时表示需要更换target了。当目前的target等于遍历到容器中的元素，那么表示出现相同的数，然后counts++，如果不同就--，当不同时，--就表示“删除”了一对不同的数据。当counts==0时，表示target代表的数也应该被删除，然后再赋予另一个值。

很奇妙的方法！

方法三

使用map或者是散列表

int findTarget3(vector<int> source)
{
    map<int,int> memo;
    for(int i:source)
    {
        memo[i]++;
    }

    for(map<int,int>::iterator it = memo.begin();it != memo.end();it++)
    {
        if(it->second >source.size()/2)
        {
            return it->first;
        }
    }
    return -1;  
}

方法四

快拍的思想，因为时超过一般的数一样，所以，如果排序以后，中点的数就是我们需要的。
所以使用快排，如果分割元素的下标是中点，那么该元素就是所求，否则，就去包含中点的那一半。

但是，当该数出现次数为1/4的时候，还是需要使用map吧。如果采用删除数的方式，那么需要更改原来的数组，或者添加一个memo，那么还不如直接使用map

意外收获

clang不支持

vector<int>  i{1,2,3,4};

回报错。