首页 > 代码库 > 算法之找出数组中出现次数大于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的元素