给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
示例 1：
输入：[3,2,3] 输出：[3]
示例 2：
输入：nums = [1] 输出：[1]
示例 3：
输入：[1,1,1,3,3,2,2,2] 输出：[1,2]
提示：
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
摩尔投票法。
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
n1 = n2 = 0
m1, m2 = 0, 1
for m in nums:
if m == m1:
n1 += 1
elif m == m2:
n2 += 1
elif n1 == 0:
m1, n1 = m, 1
elif n2 == 0:
m2, n2 = m, 1
else:
n1, n2 = n1 - 1, n2 - 1
return [m for m in [m1, m2] if nums.count(m) > len(nums) // 3]class Solution {
public List<Integer> majorityElement(int[] nums) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
for (int m : nums) {
if (m == m1) {
++n1;
} else if (m == m2) {
++n2;
} else if (n1 == 0) {
m1 = m;
++n1;
} else if (n2 == 0) {
m2 = m;
++n2;
} else {
--n1;
--n2;
}
}
List<Integer> ans = new ArrayList<>();
n1 = 0;
n2 = 0;
for (int m : nums) {
if (m == m1) {
++n1;
} else if (m == m2) {
++n2;
}
}
if (n1 > nums.length / 3) {
ans.add(m1);
}
if (n2 > nums.length / 3) {
ans.add(m2);
}
return ans;
}
}class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
for (int m : nums)
{
if (m == m1) ++n1;
else if (m == m2) ++n2;
else if (n1 == 0)
{
m1 = m;
++n1;
}
else if (n2 == 0)
{
m2 = m;
++n2;
}
else
{
--n1;
--n2;
}
}
vector<int> ans;
if (count(nums.begin(), nums.end(), m1) > nums.size() / 3) ans.push_back(m1);
if (count(nums.begin(), nums.end(), m2) > nums.size() / 3) ans.push_back(m2);
return ans;
}
};func majorityElement(nums []int) []int {
var n1, n2 int
m1, m2 := 0, 1
for _, m := range nums {
if m == m1 {
n1++
} else if m == m2 {
n2++
} else if n1 == 0 {
m1, n1 = m, 1
} else if n2 == 0 {
m2, n2 = m, 1
} else {
n1, n2 = n1-1, n2-1
}
}
n1, n2 = 0, 0
for _, m := range nums {
if m == m1 {
n1++
} else if m == m2 {
n2++
}
}
var ans []int
if n1 > len(nums)/3 {
ans = append(ans, m1)
}
if n2 > len(nums)/3 {
ans = append(ans, m2)
}
return ans
}public class Solution {
public IList<int> MajorityElement(int[] nums) {
int n1 = 0, n2 = 0;
int m1 = 0, m2 = 1;
foreach (int m in nums)
{
if (m == m1)
{
++n1;
}
else if (m == m2)
{
++n2;
}
else if (n1 == 0)
{
m1 = m;
++n1;
}
else if (n2 == 0)
{
m2 = m;
++n2;
}
else
{
--n1;
--n2;
}
}
var ans = new List<int>();
ans.Add(m1);
ans.Add(m2);
return ans.Where(m => nums.Count(n => n == m) > nums.Length / 3).ToList();
}
}