初级摩尔投票算法;
文章目录
int majorityElement(int\* nums, int numsSize){
int count=0 ,i;
int target=nums\[0\];
for(i=0;i<numsSize;i++)
{
if(count==0)
{
target=nums\[i\];
}
if(nums\[i\]==target)
count++;
else
count--;
}
if(count>0)
return target;
else
return 0;
}
思路: 当建设存在一个number 它的count>numbersize/2;则两个不同的数相遇时消去时最后剩下的就是mian number;
或则对一个为 mainnumber 的数而言两两配对(为奇数时最后三个两两配对 ) 必有相同的miannumber
eg 1 2 5 9 5 5 5
1step 5 9 5 5 5
2 step 5 5 5;
eg 1 1 1 2 2
1step 1 1 1 2 2
2step 1 1 2
3step 1 ;
伪代码 for(i=0;i<numsSize;i++) //建设第一个为mainnumber;
{
if(count==0)// 当为count=0 时更换mainnumber
{
target=nums[i];
}
if(nums[i]==target) 相同时就count++
count++;
else 不同时就 count--;
count--;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论