169. Majority Element
求超过数组个数一半的数
可以使用hash解决，时间复杂度为O(n)，但空间复杂度也为O(n)
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> count;
int n=nums.size();
for(int i=;i<n;i++){
if(++count[nums[i]]>n/) return nums[i];
}
return ;
}
};
使用投票法，时间复杂度为O(n)，空间复杂度为O(1)。
投票法就是记录出现的频次
leetcode是默认了有超过的，所以可以直接这样返回。像剑指offer上，还要用这个数去累加计算看是否真的超过了n/2。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int freq = ;
int res;
for(int i = ;i < nums.size();i++){
if(freq == ){
res = nums[i];
freq++;
}
else if(nums[i] == res)
freq++;
else
freq--;
}
return res;
}
};
229. Majority Element II
求个数超过n/3的数
首先明确最多只有可能有2个数超过，如果有3个数都超过了，那数组的个数肯定大于n了。
还是使用投票法。
错误写法：这个写法先去考虑了freq1、2，实际上应该首先考虑是否和当前数字相当，如果不相等再去考虑freq的问题
Input:
[1,2,2,3,2,1,1,3]
Output:
[1]
Expected:
[2,1]
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> result;
int num1,num2,freq1 = ,freq2 = ;
for(int i = ;i < nums.size();i++){
if(freq1 == ){
num1 = nums[i];
freq1++;
}
else if(nums[i] == num1)
freq1++;
else if(freq2 == ){
num2 = nums[i];
freq2++;
}
else if(nums[i] == num2)
freq2++;
else{
freq1--;
freq2--;
}
}
freq1 = ,freq2 = ;
for(int i = ;i < nums.size();i++){
if(nums[i] == num1)
freq1++;
if(nums[i] == num2)
freq2++;
}
if(freq1 > nums.size()/)
result.push_back(num1);
if(freq2 > nums.size()/ && num1 != num2)
result.push_back(num2);
return result;
}
};
正确写法：
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> result;
int num1 = ,num2 = ,freq1 = ,freq2 = ;
for(int i = ;i < nums.size();i++){
if(nums[i] == num1)
freq1++;
else if(nums[i] == num2)
freq2++;
else if(freq1 == ){
num1 = nums[i];
freq1++;
}
else if(freq2 == ){
num2 = nums[i];
freq2++;
}
else{
freq1--;
freq2--;
}
}
freq1 = ,freq2 = ;
for(int i = ;i < nums.size();i++){
if(nums[i] == num1)
freq1++;
else if(nums[i] == num2)
freq2++;
}
if(freq1 > nums.size()/)
result.push_back(num1);
if(freq2 > nums.size()/)
result.push_back(num2);
return result;
}
};