# [LeetCode] 229. Majority Element II 多数元素 II

2021年09月15日 阅读数：1

Given an integer array of size n, find all elements that appear more than `⌊ n/3 ⌋` times.html

Note: The algorithm should run in linear time and in O(1) space.java

Example 1:python

```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的元素，而且限定了时间和空间复杂度，所以不能排序，不能使用哈希表。app

Java:url

```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)
if (count2 > len / 3)
return result;
}　　```

Python:spa

```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:code

```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++:htm

```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 多数元素