题目
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii
给定一个大小为 n 的整数数组，找出其中所有出现超过 ? n/3? 次的元素。
示例 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
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
解法
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
n = len(nums)
if n == 1:
return nums
target = n//3
res = []
d = {}
for i in range(n):
num = nums[i]
if num in d:
d[num] += 1;
else:
d[num] = 1
if d[num] > target and num not in res:
res.append(num)
return res
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
vector<int> ans;
unordered_map<int, int> cnt;
for(auto &v: nums)
{
cnt[v]++;
}
for (auto & v: cnt)
{
if(v.second > n/3)
{
ans.push_back(v.first);
}
}
return ans;
}
};
- 方法2-摩尔投票法，
有一个对摩尔投票法非常形象的比喻：多方混战。
首先要知道，在任何数组中，出现次数大于该数组长度1/3的值最多只有两个。
我们把这道题比作一场多方混战，战斗结果一定只有最多两个阵营幸存，其他阵营被歼灭。数组中的数字即代表某士兵所在的阵营。
我们维护两个潜在幸存阵营A和B。我们遍历数组，如果遇到了属于A或者属于B的士兵，则把士兵加入A或B队伍中，该队伍人数加一。继续遍历。
如果遇到了一个士兵既不属于A阵营，也不属于B阵营，这时有两种情况：
情况一：A阵营和B阵营都还有活着的士兵，那么进行一次厮杀，参与厮杀的三个士兵全部阵亡：A阵营的一个士兵阵亡，B阵营的一个士兵阵亡，这个不知道从哪个阵营来的士兵也阵亡。继续遍历。
情况二：A阵营或B阵营已经没有士兵了。没有士兵的阵营暂时从地球上消失了。那么把当前遍历到的新士兵算作新的潜在幸存阵营，这个新阵营只有他一个人。继续遍历。
大战结束，最后A和B阵营就是初始人数最多的阵营。判断一下A，B的人数是否超过所有人数的三分之一就行了。
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
ans = []
element1, element2 = 0, 0
vote1, vote2 = 0, 0
for num in nums:
if vote1 > 0 and num == element1:
vote1 += 1
elif vote2 > 0 and num == element2:
vote2 += 1
elif vote1 == 0:
element1 = num
vote1 += 1
elif vote2 == 0:
element2 = num
vote2 += 1
else:
vote1 -= 1
vote2 -= 1
cnt1, cnt2 = 0, 0
for num in nums:
if vote1 > 0 and num == element1:
cnt1 += 1
if vote2 > 0 and num == element2:
cnt2 += 1
if vote1 > 0 and cnt1 > len(nums) / 3:
ans.append(element1)
if vote2 > 0 and cnt2 > len(nums) / 3:
ans.append(element2)
return ans
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> ans;
int element1 = 0;
int element2 = 0;
int vote1 = 0;
int vote2 = 0;
for (auto & num : nums) {
if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
vote1++;
} else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
vote2++;
} else if (vote1 == 0) { // 选择第一个元素
element1 = num;
vote1++;
} else if (vote2 == 0) { // 选择第二个元素
element2 = num;
vote2++;
} else { //如果三个元素均不相同，则相互抵消1次
vote1--;
vote2--;
}
}
int cnt1 = 0;
int cnt2 = 0;
for (auto & num : nums) {
if (vote1 > 0 && num == element1) {
cnt1++;
}
if (vote2 > 0 && num == element2) {
cnt2++;
}
}
// 检测元素出现的次数是否满足要求
if (vote1 > 0 && cnt1 > nums.size() / 3) {
ans.push_back(element1);
}
if (vote2 > 0 && cnt2 > nums.size() / 3) {
ans.push_back(element2);
}
return ans;
}
};
复杂度分析
- 时间复杂度：O(n), O(n)
- 空间复杂度：O(n), O(1)
参考
|