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]
169. Majority Element 的拓展，这题要求的是出现次数大于n/3的元素，并且限定了时间和空间复杂度，因此不能排序，不能使用哈希表。
解法：Boyer-Moore多数投票算法 Boyer–Moore majority vote algorithm，T：O(n) S: O(1) 摩尔投票法 Moore Voting
Java:
public List<Integer> majorityElement(int[] nums) {
if (nums == null || nums.length == 0)
return new ArrayList<Integer>();
List<Integer> result = new ArrayList<Integer>();
int number1 = nums[0], number2 = nums[0], count1 = 0, count2 = 0, len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
else if (count1 == 0) {
number1 = nums[i];
count1 = 1;
} else if (count2 == 0) {
number2 = nums[i];
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
}
if (count1 > len / 3)
result.add(number1);
if (count2 > len / 3)
result.add(number2);
return result;
} Python:
class Solution:
# @param {integer[]} nums
# @return {integer[]}
def majorityElement(self, nums):
if not nums:
return []
count1, count2, candidate1, candidate2 = 0, 0, 0, 1
for n in nums:
if n == candidate1:
count1 += 1
elif n == candidate2:
count2 += 1
elif count1 == 0:
candidate1, count1 = n, 1
elif count2 == 0:
candidate2, count2 = n, 1
else:
count1, count2 = count1 - 1, count2 - 1
return [n for n in (candidate1, candidate2)
if nums.count(n) > len(nums) // 3]
Python:
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
k, n, cnts = 3, len(nums), collections.defaultdict(int) for i in nums:
cnts[i] += 1
# Detecting k items in cnts, at least one of them must have exactly
# one in it. We will discard those k items by one for each.
# This action keeps the same mojority numbers in the remaining numbers.
# Because if x / n > 1 / k is true, then (x - 1) / (n - k) > 1 / k is also true.
if len(cnts) == k:
for j in cnts.keys():
cnts[j] -= 1
if cnts[j] == 0:
del cnts[j] # Resets cnts for the following counting.
for i in cnts.keys():
cnts[i] = 0 # Counts the occurrence of each candidate integer.
for i in nums:
if i in cnts:
cnts[i] += 1 # Selects the integer which occurs > [n / k] times.
result = []
for i in cnts.keys():
if cnts[i] > n / k:
result.append(i) return result def majorityElement2(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
return [i[0] for i in collections.Counter(nums).items() if i[1] > len(nums) / 3]
C++:
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
int m = 0, n = 0, cm = 0, cn = 0;
for (auto &a : nums) {
if (a == m) ++cm;
else if (a ==n) ++cn;
else if (cm == 0) m = a, cm = 1;
else if (cn == 0) n = a, cn = 1;
else --cm, --cn;
}
cm = cn = 0;
for (auto &a : nums) {
if (a == m) ++cm;
else if (a == n) ++cn;
}
if (cm > nums.size() / 3) res.push_back(m);
if (cn > nums.size() / 3) res.push_back(n);
return res;
}
};
C++:
vector<int> majorityElement(vector<int>& nums) {
int cnt1 = 0, cnt2 = 0, a=0, b=1;
for(auto n: nums){
if (a==n){
cnt1++;
}
else if (b==n){
cnt2++;
}
else if (cnt1==0){
a = n;
cnt1 = 1;
}
else if (cnt2 == 0){
b = n;
cnt2 = 1;
}
else{
cnt1--;
cnt2--;
}
}
cnt1 = cnt2 = 0;
for(auto n: nums){
if (n==a) cnt1++;
else if (n==b) cnt2++;
}
vector<int> res;
if (cnt1 > nums.size()/3) res.push_back(a);
if (cnt2 > nums.size()/3) res.push_back(b);
return res;
}
类似题目：
[LeetCode] 169. Majority Element 多数元素