江苏网站建设哪家好,推荐优秀的企业网站设计,信誉好的专业网站建设,不要随意去注册一个公司这里先贴题目#xff1a; Boyer-Moore 投票算法#xff1a;
通俗点来讲#xff0c;就是占领据点#xff0c;像攻城那样#xff0c;对消。
当你的据点有人时对消#xff0c;无人时就占领。 这道题使用该算法可实现时间复杂度为O(n),空间复杂度为O(1)#xff0c;接下来看…这里先贴题目 Boyer-Moore 投票算法
通俗点来讲就是占领据点像攻城那样对消。
当你的据点有人时对消无人时就占领。 这道题使用该算法可实现时间复杂度为O(n),空间复杂度为O(1)接下来看代码
int majorityElement(int* nums, int numsSize) {int amzing nums[0];int count 0;for (int i 0; i numsSize; i){if (amzing nums[i])count;else if (count 0){amzing nums[i];count;}elsecount--;}return amzing;
} 我们定义一个amzing先记录数组第一个数字并且数量为0然后遍历整个数组当count不为0时数字不同时相消数字相同时增加当count为0时amzing换其他数字再增加数量。
通俗点讲定义一个士兵数量为0遍历所有人当count不为0如果数字不同就是遇到敌人同归于尽数字相同遇到友军就加入。当count等于0据点无人哪个数字也可以占领。但是有一个阵营的人数占了大半无论怎么对拼相消剩下的一定是那个阵营的也就是那个大半的数字。
排序
int cmp(void* p1,void* p2)
{return *(int*)p1 - *(int*)p2;
}int majorityElement(int* nums, int numsSize){qsort(nums,numsSize,4,cmp);return nums[numsSize/2];
}
