首页 > 代码库 > Majority Element II
Majority Element II
https://leetcode.com/problems/majority-element-ii/#/description
挑出所有大于n/3 的数，两个很相似的题，但是这次的major 是> n/3 而且是要挑出‘所有’
hash 表和排序依然可以，但是题目要求O(n) 就没办法了。
majority vote 的修改版：这个算法是一次投两个数而不是一个，这样我们可以投出两个major，而因为是n/3，所以最多只有两个major。
故函数返回要么是空，要么有1 个元素，要么有2 个。用majority vote 算法vote 出两个major 但是却不能保证他们大于n/3，所以要再遍历一次，确保>n/3 以后再添加到返回结果里。
var majorityElement = function(nums) { var t1, t2, n1 = 0, n2 = 0; var len = nums.length; for (var i = 0; i < len; i++) { if (t1 === nums[i]) { n1++; continue; } if (t2 === nums[i]) { n2++; continue; } if (n1 === 0) { t1 = nums[i]; n1 = 1; continue; } if (n2 === 0) { t2 = nums[i]; n2 = 1; continue; } n1--; n2--; } var z1 = 0, z2 = 0; for (var i = 0; i < len; i++) { if (n1 > 0 && nums[i] === t1) { z1++; continue; } if (n2 > 0 && nums[i] === t2) { z2++; continue; } } var ret = []; if (z1 > len / 3) ret.push(t1); if (z2 > len / 3) ret.push(t2); return ret;}
Majority Element II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。