Open Shawngbk opened 7 years ago
有一种算法叫 Moore’s Voting Algorithm，由Robert S.Boyer 和J Strother Moore于1980年发明，是线性时间复杂度。
当然，这种算法对于存在主元素的数组是有效的，如：
A A A C C B B C C C B C C
它肯定能返回主元素C。但是，如果不存在主元素，那么得到的结果就跟遍历顺序有关了。如:
A A A C C C B
如果是从左到右，那么结果是B，如果是从右到左，那么结果是A。 参考：https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation
public class Solution { public int majorityElement(int[] nums) { int count = 0; int res = 0; for(int i = 0; i < nums.length; i ++) { if(count == 0) { res = nums[i]; count = 1; } else if(res == nums[i]) { count ++; } else { count --; } } return res; } }
考
Shawngbk
commented
7 years ago Shawngbk
commented
7 years ago
有一种算法叫 Moore’s Voting Algorithm，由Robert S.Boyer 和J Strother Moore于1980年发明，是线性时间复杂度。
当然，这种算法对于存在主元素的数组是有效的，如：
A A A C C B B C C C B C C
它肯定能返回主元素C。但是，如果不存在主元素，那么得到的结果就跟遍历顺序有关了。如:
A A A C C C B
如果是从左到右，那么结果是B，如果是从右到左，那么结果是A。 参考：https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation
public class Solution { public int majorityElement(int[] nums) { int count = 0; int res = 0; for(int i = 0; i < nums.length; i ++) { if(count == 0) { res = nums[i]; count = 1; } else if(res == nums[i]) { count ++; } else { count --; } } return res; } }