首页 > 代码库 > LeetCode 4 :Majority Element
LeetCode 4 :Majority Element
problem：Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
problem analysis:
1.首先，需要统计数组元素出现的次数，包括不同的元素有几个？每一个不同的元素出现了几次？同时需要将不同的元素及出现的频率正确对应。
2.在第一步完成之后，可以寻找最大的频率数，然后找到majority element。
代码写的有点乱，有待优化。
class Solution{public: int majorityElement(vector<int> &num) { vector<int> elemFre; vector<int> elemCount(num.size(), 0); int vecSize = num.size()/2; int tempInt = 0; int vecPos = 0; int noMatchNum = 0; int elemSize = 0; for(vector<int>::iterator iter=num.begin(); iter!=num.end(); ++iter) { if(iter == num.begin()) { elemFre.push_back(*iter); } for(vector<int>::iterator iterFre=elemFre.begin(); iterFre!=elemFre.end(); ++iterFre) { if((*iter) == (*iterFre)) { elemCount[noMatchNum] += 1; } else { ++noMatchNum; continue; } } elemSize = elemFre.size(); if(noMatchNum == elemSize) { elemFre.push_back(*iter); elemCount[noMatchNum] += 1; } noMatchNum = 0; } vecPos = 0; for(vector<int>::iterator iter=elemCount.begin(); iter!=elemCount.end(); ++iter,++vecPos) { if((*iter) > vecSize) { tempInt = elemFre[vecPos]; } else { continue; } } return tempInt; }};
第一个两重for循环建立一个元素及其频率的对应表，elemFre存储的是num中不同的元素，elemCount存储的是elemFre里面元素出现的频率。
1.第一次循环，把第一个元素添加到elemFre,进入内层循环中。
2.内层循环，遍历elemFre中的所有元素，分两种情况：a,num中的元素在elemFre中找到了对应项，则对应的频率数组elemCount[noMatchNum]+1；否则noMatchNum+1.直到将elemFre中所有的元素都遍历完。
3.循环结束后，noMatchNum中应该存放的是与当前元素都不同的之前出现的元素数目，或者是当前元素在elemFre中的对应项前面的元素数目。
4.在上面的基础上判断noMatchNum == elemFre.size(),如果相等，则说明新到元素需要添加到elemFre中，并且对应的频率数+1，具体完成这一操作的是
if(noMatchNum == elemSize)
{
elemFre.push_back(*iter);
elemCount[noMatchNum] += 1;
}
noMatchNum = 0;
这样通过上面的操作完成的不同元素的提取，和对应频率数目的统计工作。
5.通过以上操作，在遍历一次elemCount，找到最大的频率数并返回对应的元素即可。
总计：逻辑思维不够，思维不严谨，变量的最终结果意义不明确，浮躁。
我这个方法肯定不是最好的，欢迎大家推荐优化的算法。
LeetCode 4 :Majority Element