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; }

?

轉載于:https://www.cnblogs.com/agentgamer/p/7019837.html

總結

以上是生活随笔為你收集整理的Majority Element II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。