摩尔投票法

摩尔投票法

该题默认存在占比多于一半的元素，故该元素的数量 - 其他元素的数量 > 0,可用摩尔投票法。

思路:

候选元素(cur)初始化为nums[0]，票数cnt初始化为1。当遇到与cur相同的数，则票数cnt++，否则票数cnt- -。当票数cnt为0时，更换候选元素，并将票数cnt重置为1。

int majorityElement(vector& nums) { int cnt = 1; int cur = nums[0]; for(int i = 1; i < nums.size(); i++){ if(cur == nums[i]){ cnt++; }else{ cnt--; if(cnt == 0){ cur = nums[i+1];//更换候选元素 } } } return cur; }

而现在这题则可能不存在占比多于一半的元素，若还是使用上述的方法，会存在下面两种问题：

当数组为[2,2,1,1]时，遍历到最后一个元素，cnt此时为0，更换候选元素，则导致越界。基于此，我们加上越界判断。当数组为[2,2,1,1,3]时，此时不存在占比多于一半的元素。遍历到倒数第二个元素时，cnt此时为0，更换候选元素，cur = 3，导致最后返回元素为3，而不是-1。基于此，我们判断最后得到的候选元素出现的频率即可。

int majorityElement(vector& nums) { map mp; for(int num : nums){ mp[num]++; } int cur = nums[0]; int cnt = 1; for(int i = 1; i < nums.size(); i++){ if(cur == nums[i]){ cnt++; }else{ cnt--; if(cnt == 0){ if(i + 1 == nums.size()){ return -1;//越界则说明遍历完了，cnt却为0，不存在主要元素 } cur = nums[i+1]; } } } //若存在多数元素，此时的cur一定是多数元素 return mp[cur] > nums.size()/2 ? cur : -1; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。