首页 > 代码库 > 算法之找出数组中出现次数大于n/m的元素

算法之找出数组中出现次数大于n/m的元素

最经典的题目莫过于是: 在一个数组中找出出现次数超过n/2的元素?更进一步的,找出数组中出现次数大于n/3的所有元素?

注:这里有一个很重要的事实,那就是出现次数大于n/m的元素的个数至多为(m-1)个,比如出现次数大于n/3的至多只有两个。

关于这一类题目的解题思路,可以先讲一个游戏 称作 “俄罗斯方块”。这里的规则是每一行的元素要完全不一样,一样的元素则总是在同一列,如果最下面的行已经被填满,那么消除最下面的行。

例如在数组 A = {7,3,3,7,4,3,4,7,3,4,3,4,7,3,4} Len = 15,现在找出现次数大于 Len/3的,也就是出现超过5次的。那么现在我们的方块的宽度就应该是3,即每一步的状态一次为

                                                                                               

                         3                 7 3                                                     

7      7  3        7 3                 7 3 4     //现在消去最下面的一行 。               。。。。

知道没有元素可添加,并且没有元素可删除时,方块中最后还剩下的元素就有可能是大于n/m的,最后再检验一遍即可。

代码为:

typedef pair<int,int> P;

vector<int>  printMaxTwo(const vector<int> &A , const int k)
{
    typedef map<int,int>::value_type Elem;
    const int n = A.size();
    map<int,int> idxs;
    for(int i=0;i<n;++i)
    {
        if(idxs.find(A[i]) != idxs.end())
        {
            ++idxs[A[i]];
        }
        else
        {
            idxs.insert(Elem(A[i],1));
            if(idxs.size() == k)
            {
                //if there is a full level in the box
                for(auto iter = idxs.begin(); iter != idxs.end();)
                {
                    --((*iter).second);
                    if((*iter).second == 0) iter = idxs.erase(iter);
                    else ++iter;
                }
            }       
        }
    }
    //If there exists no element in the final box
    vector<int> ret;
    for(auto a: idxs) a.second = 0;
    for(auto a: A)
    {
        if(idxs.find(a) != idxs.end())
            ++idxs[a];
    }
    for(auto a: idxs)
        if(a.second >= n/k) ret.push_back(a.first);
    return ret;
}

值得一提的是,上述代码中,如果最终的hash表内没有元素,并不能说明没有元素出现n/m次,为什么呢,比如,元素的个数是15,其中有2,3,5,三个元素每个出现5次,那么这并不能说明出现此处大于或等于n/m的没有,而是有3个。

但是一般需要求的是大于n/m的,上述情况也只有在整除时才会出现,那么可以忽略上述情况了。


                                  



算法之找出数组中出现次数大于n/m的元素