Problem
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?
Solution
/**
* @param {number[]} nums
* @return {number[]}
*/
var majorityElement = function(nums) {
var num1 = Number.MAX_SAFE_INTEGER;
var count1 = 0;
var num2 = Number.MAX_SAFE_INTEGER;
var count2 = 0;
for (var i = 0; i < nums.length; i++) {
if (nums[i] === num1) {
count1 += 1;
} else if (nums[i] === num2) {
count2 += 1;
} else if (count1 === 0) {
num1 = nums[i];
count1 += 1;
} else if (count2 === 0) {
num2 = nums[i];
count2 += 1;
} else {
count1 -= 1;
count2 -= 1;
}
}
var realCount1 = 0;
var realCount2 = 0;
for (var i = 0; i < nums.length; i++) {
if (nums[i] === num1) realCount1++;
if (nums[i] === num2) realCount2++;
}
return (realCount1 > nums.length / 3) && (realCount2 > nums.length / 3)
? [num1, num2]
: ((realCount1 > nums.length / 3) ? [num1] : ((realCount2 > nums.length / 3) ? [num2] : []))
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).