一：Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
class Solution {
public:
int majorityElement(vector<int>& nums) {
int numsSize = nums.size();
int times = ;
int res = ;
for(int i=;i<nums.size();i++){
if(i==){
res = nums[i];
times = ;
}else{
if(nums[i]!=res){
times--;
if(times==){
res = nums[i];
times = ;
}
}else{
times++;
}
}
}
return res;
}
};二：Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
出现 ⌊ n/3 ⌋的数，在数组中至多只有两个，可以画图理解。
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
int numsSize = nums.size();
int resval1 = ,resval2=;
int times1 = ,times2=;
for(int i=;i<numsSize;i++){
if(i==){
resval1 = nums[i];
times1++;
}else{
if(nums[i]==resval1){
times1++;
}else if(times2==){
times2=;
resval2 = nums[i];
}else if(nums[i]==resval2){
times2++;
}else{
times1--;
times2--;
if(times1==){
times1=;
resval1=nums[i];
}
}
}
}
int cnt1=,cnt2=;
for(int i=;i<numsSize;i++){
if(nums[i]==resval1)
cnt1++;
if(nums[i]==resval2)
cnt2++;
}
if(cnt1>(numsSize/))
res.push_back(resval1);
if(cnt2!=numsSize && cnt2>(numsSize/))
res.push_back(resval2);
return res;
}
};