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]
Solution: Boyer–Moore Voting Algorithm
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Author: Huahua class Solution { public: vector<int> majorityElement(vector<int>& nums) { int n1 = 0; int c1 = 0; int n2 = 1; int c2 = 0; for (int num : nums) { if (num == n1) { ++c1; } else if (num == n2) { ++c2; } else if (c1 == 0) { n1 = num; c1 = 1; } else if (c2 == 0) { n2 = num; c2 = 1; } else { --c1; --c2; } } c1 = c2 = 0; for (int num : nums) { if (num == n1) ++c1; else if (num == n2) ++c2; } const int c = nums.size() / 3; vector<int> ans; if (c1 > c) ans.push_back(n1); if (c2 > c) ans.push_back(n2); return ans; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Author: Huahua class Solution: def majorityElement(self, nums: List[int]) -> List[int]: n1, c1, n2, c2 = 0, 0, 1, 0 for num in nums: if num == n1: c1 += 1 elif num == n2: c2 += 1 elif c1 == 0: n1, c1 = num, 1 elif c2 == 0: n2, c2 = num, 1 else: c1, c2 = c1 - 1, c2 -1 c1, c2 = 0, 0 for num in nums: if num == n1: c1 += 1 elif num == n2: c2 += 1 ans = [] if c1 > len(nums) // 3: ans.append(n1) if c2 > len(nums) // 3: ans.append(n2) return ans |