46. 主元素解1解2
给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。假定一定存在这样的主元素。 样例 给出数组[1,1,1,1,2,2,2]，返回 1
解1
如果不要求空间复杂度和时间复杂度的话，最简单的方法就是放入map种统计次数，然后把次数大于一半size的拿出来就可以了。
int majorityNumber(vector<int> &nums) {
map<int,int> res_num;
for(auto vv:nums)
{
res_num[vv]++;
}
for(auto rr:res_num)
{
if(rr.second>nums.size()/2)
return rr.first;
}
// write your code here
}如果要求一遍遍历，空间复杂度为O（1）呢，我也是没想到太好的方法，查了查别人的做法，有个很值得参考，总结如下：
解2
注意到这么一个事实，主元素出现的次数减去其他所有元素出现的次数总是大于0的，那么我们删除任意两个不同的元素，剩余的数组的主元素依然是整个数组的主元素。代码实现的话肯定不是真的删除，合适的时候更新字数组的位置。我也是看了一会才看懂。 我们先假定第一个数nums[0]为主元素，这个数和其他数出现的次数之差记作dif，初始化为1，从第二个数开始遍历，如果和当前主元素相同，那么dif++，否则dif--，若dif为0的话就更新主元素这个时候前面肯定是偶数个数而且没两个数都是不相同的，所有这样进行遍历之后是可找到主元素的。考虑两种特殊情况，就是都删除倒最后： 如果是奇数个数，那么如果只剩下一个，那么这个数肯定是主元素。 如果是偶数个数，那么剩下两个的话，那么这两个数肯定是一样的，且为主元素，要不就不存在主元素了。 code：
int majorityNumber(vector<int> &nums)
{
int res=nums[0];
int dif=1;
for(int i=1;i<nums.size()-1;i++)
{
if(res==nums[i])
dif++;
else
dif--;
if(dif==0)
res=nums[i+1];
}
return res;
}over
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.11.30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录