# 229 Majority Element II
記得先想 Edge Case
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋
times.
Note: The algorithm should run in linear time and in O(1) space.
Example 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
如何解
第一個想法就是把數字存進 obj 裡,然後哪一個 > 1/3 次就會丟進結果,這樣 Big O(n) 解決
var majorityElement = function(nums) {
let obj = {};
let len = nums.length;
let judge = len/3;
let result = []
for(let i = 0; i<len; i++){
if(obj[ nums[i] ]) {
// if( count > judge)
if(obj[ nums[i] ] + 1 > judge){
result.push( nums[i] )
}else {
obj[ nums[i] ] ++;
}
}else {
obj[ nums[i] ] = 1;
}
}
return [...result];
};
但像 [1] 或 [1, 2] 這種 case 就會失效,但又怕重覆 [2, 2] 所以我必須新增一個 set 去存 result
var majorityElement = function(nums) {
let obj = {};
let len = nums.length;
let judge = len/3;
let result = new Set();
for(let i = 0; i<len; i++){
if(obj[ nums[i] ]) {
if(obj[ nums[i] ] + 1 > judge){
// add Here
result.add( nums[i] )
}else {
obj[ nums[i] ] ++;
}
}else {
obj[ nums[i] ] = 1;
// add Here
if(obj[ nums[i] ] > judge){
result.add( nums[i] )
}
}
}
return [...result];
};
更佳解?
前面寫法其實有點亂因為一堆 if else for,換成以下寫法清楚超多
if(obj[ nums[i] ]) {
obj[ nums[i] ] ++;
}else {
obj[ nums[i] ] = 1;
}
// --可以用以下取代----------
(nums[i] in obj) ? obj[ nums[i] ] ++ : obj[ nums[i] ] = 1;
var majorityElement = function(nums) {
let obj = {};
let len = nums.length;
let judge = len/3;
let result = [];
for(let i = 0; i<len; i++){
(nums[i] in obj) ? obj[ nums[i] ] ++ : obj[ nums[i] ] = 1;
}
Object.keys(obj).forEach( key => {
if(obj[key] > judge) result.push(key)
})
return result;
};
Last updated
Was this helpful?