# 229.Majority Element II

229.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.

Hint:

How many majority elements could it possibly have?

class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int curIndex1=0,curIndex2=0,count1=0,count2=0;
int size=nums.size(),i=0,tri=size/3;
vector<int>res;
for(i=0;i<nums.size();i++){
if(nums[i]==nums[curIndex1])
count1++;
else if(nums[i]==nums[curIndex2])
count2++;
else if(!count1){
count1=1;
curIndex1=i;
}
else if(!count2){
count2=1;
curIndex2=i;
}
else{
count1--;
count2--;
}
}
count1=0;
count2=0;
for(i=0;i<nums.size();i++){
if(nums[i]==nums[curIndex1])
count1++;
else if(nums[i]==nums[curIndex2])
count2++;
}
if(count1>tri)
res.push_back(nums[curIndex1]);
if(count2>tri)
res.push_back(nums[curIndex2]);
return res;
}
};


# 219.Contains Duplicate II

219.Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> hash_table;
int i=0;
for(i=0;i<nums.size();i++){
if(hash_table.find(nums[i])!=hash_table.end()&&i-hash_table[nums[i]]<=k)
return true;
hash_table[nums[i]]=i;
}
return false;
}
};

• [ TODO Contains Duplicate III]

# 217.Contains Duplicate I

217.Contains Duplicate I

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if(nums.size()==0||nums.size()==1)
return false;
sort(nums.begin(),nums.end());
int i=0;
for(i;i<nums.size();i++){
if(nums[i]==nums[i+1])
return true;
}
return false;
}
};


# 209.Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
if(nums.empty())
return 0;
int i=0,j=0,size=nums.size(),sum=0,min_size=INT_MAX;
for(i=0;i<size;i++){
while(sum<s){
sum+=nums[++j];
}
min_size=min(min_size,j-i+1);
}
return min_size==INT_MAX ? 0:min_size;
}
};


# 189.Rotate Array

189.Rotate Array

• [ TODO 189 use constant space to finish it] Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(k<=0)
return;
int size=nums.size(),i=0;
vector<int>nums2(nums.begin(),nums.end());
for(i=0;i<size;i++){
nums[(i+k)%size]=nums2[i];
}
}
};