Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Follow-up: Could you solve the problem in linear time and in O(1) space?
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109
我的答案:时间、空间复杂度O(n)
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int length = nums.size();
unordered_map<int, int> count;
unordered_set<int> screen_out;
for (const auto& n:nums) {
if (screen_out.find(n) == screen_out.end()) {
if (count.find(n) == count.end()) {
count[n] = 1;
}
else {
++count[n];
}
if (count[n] > length/3) {
screen_out.insert(n);
}
}
}
vector<int> ans(screen_out.begin(), screen_out.end());
return ans;
}
};
Runtime: 40 ms, faster than 26.49% of C++ online submissions for Majority Element II.
Memory Usage: 16.5 MB, less than 7.86% of C++ online submissions for Majority Element II.
有点慢
看答案:
https://zxi.mytechroad.com/blog/algorithms/array/leetcode-229-majority-element-ii/
Solution: Boyer–Moore Voting Algorithm
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int length = nums.size();
unordered_map<int, int> count;
vector<int> ans;
// ans.reserve(2);
for (const auto& n:nums) {
if (find(ans.begin(), ans.end(), n) == ans.end()) {
if (count.find(n) == count.end()) {
count[n] = 1;
}
else {
++count[n];
}
if (count[n] > length/3) {
ans.push_back(n);
if (ans.size() == 2) break;
}
}
}
return ans;
}
};
Runtime: 32 ms, faster than 51.59% of C++ online submissions for Majority Element II.
Memory Usage: 16.3 MB, less than 7.86% of C++ online submissions for Majority Element II.
看了答案之后发现,最多有2个元素输出
做了点优化
答案Boyer-Moore算法:
// 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;
}
};
Runtime: 28 ms, faster than 76.28% of C++ online submissions for Majority Element II.
Memory Usage: 16.1 MB, less than 23.62% of C++ online submissions for Majority Element II.
问题:
为什么要重新计数?
https://www.youtube.com/watch?v=FGwCv6JAZQ8
实验了一下,果然出错了!主要是count可能会降到0,这时候有可能整个需要,有可能不需要
然后上面的代码其实有点tricky,n1和n2需要初始化,但是要初始化成两个不一样的数字,类似前面都搜索过一段了,但是刚好两个counter都清零的结果。否则如果n1=n2=0,然后输入都是0,那么第二个for循环的第二个if就得是else if,这样也行。
最后是,第一个for loop里面if和else if的顺序,必须把n1和n2的判断放到最前面,否则
for (const auto& n:nums){
if (c1 == 0) {
n1 = n;
++c1;
}
else if (c2 == 0) {
n2 = n;
++c2;
}
else if (n == n1) ++c1;
else if (n == n2) ++c2;
else {
--c1;
--c2;
}
}
比如连续两个1输入,[1,1,...],那么第二个1就会把c2也占了,而且本身的计数也会少加了1
cout << n << ", " << n1 << ", " << c1 << ", " << n2 << ", " << c2 << endl;
错误结果:
1, 1, 1, 2147483647, 0
1, 1, 1, 1, 1
2, 1, 0, 1, 0 <~ “那么第二个1就会把c2也占了,而且本身的计数也会少加了1”
3, 3, 1, 1, 0
4, 3, 1, 4, 1
1, 3, 0, 4, 0
1, 1, 1, 4, 0
5, 1, 1, 5, 1
6, 1, 0, 5, 0
7, 7, 1, 5, 0
1, 7, 1, 1, 1
1, 7, 1, 1, 2
8, 7, 0, 1, 1
9, 9, 1, 1, 1
10, 9, 0, 1, 0
1, 1, 1, 1, 0
11, 1, 1, 11, 1
12, 1, 0, 11, 0
13, 13, 1, 11, 0
14, 13, 1, 14, 1
正确结果
1, 1, 1, 2147483647, 0
1, 1, 2, 2147483647, 0
2, 1, 2, 2, 1
3, 1, 1, 2, 0
4, 1, 1, 4, 1
1, 1, 2, 4, 1
1, 1, 3, 4, 1
5, 1, 2, 4, 0
6, 1, 2, 6, 1
7, 1, 1, 6, 0
1, 1, 2, 6, 0
1, 1, 3, 6, 0
8, 1, 3, 8, 1
9, 1, 2, 8, 0
10, 1, 2, 10, 1
1, 1, 3, 10, 1
11, 1, 2, 10, 0
12, 1, 2, 12, 1
13, 1, 1, 12, 0
14, 1, 1, 14, 1
回顾169. Majority Element
Boyer moore的写法是:
// https://zxi.mytechroad.com/blog/divide-and-conquer/leetcode-169-majority-element/
class Solution {
public:
int majorityElement(vector<int>& nums) {
int majority = nums.front();
int count = 0;
for (const int num : nums) {
if (num == majority) ++count;
else if (--count == 0) {
count = 1;
majority = num;
}
}
return majority;
}
};
这里的count判断和num不需要注意前后顺序,因为只有一个count
我自己的写的版本,过了测试
class Solution {
public:
int majorityElement(vector<int>& nums) {
int majority = nums.front();
int count = 0;
for (const int num : nums) {
if (count == 0) {
++count;
majority = num;
}
else if (num == majority) ++count;
else --count;
}
return majority;
}
};
网友评论