https://leetcode.com/problems/find-all-duplicates-in-an-array/description/
Solution 1. swap number i to index i-1
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
int i=0;
while(i<nums.size()) {
if(nums[i] != nums[nums[i]-1])
swap(nums[i], nums[nums[i]-1]);
else i++;
}
for(int i=0; i<nums.size(); i++) {
if(i+1 != nums[i]) res.push_back(nums[i]);
}
return res;
}
Solution 2. Mark by +/-
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
for(int i=0; i<nums.size(); i++) {
nums[abs(nums[i])-1] = -nums[abs(nums[i])-1];
if(nums[abs(nums[i])-1]>0) res.push_back(abs(nums[i]));
}
return res;
}
Solution 3. counting number nums[i] by adding n to index i-1
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
int n = nums.size();
for(int i=0; i<n; i++) {
nums[(nums[i]-1)%n] += n;
}
for(int i=0; i<n; i++) {
if(nums[i]>2*n) res.push_back(i+1);
}
return res;
}
Showing posts with label Duplicates. Show all posts
Showing posts with label Duplicates. Show all posts
Wednesday, September 27, 2017
Thursday, September 14, 2017
605. Can Place Flowers
https://leetcode.com/problems/can-place-flowers/description/
Solution 1. add 0 to both side for convenience.
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
if(n == 0) return true;
if(flowerbed.size() == 0) return false;
flowerbed.insert(flowerbed.begin(),0);
flowerbed.push_back(0);
for(int i=1; i<flowerbed.size()-1; i++) {
if(flowerbed[i-1] + flowerbed[i] + flowerbed[i+1] == 0) {
i++;
n--;
}
}
return n<=0;
}
Solution 2.
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
if(n == 0) return true;
if(flowerbed.size() == 0) return false;
int z = flowerbed[0] ? 0 : 2, res = 0; // a 0 at beginning counted as 2
for(int i=1; i<flowerbed.size(); i++) {
if(flowerbed[i] == 1 && flowerbed[i-1] == 0) {
res += (z-1)/2;
z = 0;
if(res>=n) return true;
}
else if(flowerbed[i] == 0 && flowerbed[i-1] == 1) {
z = 1;
}
else if(flowerbed[i] == 0) z++;
else continue;
}
res += z/2;
if(res>=n) return true;
return false;
}
Solution 1. add 0 to both side for convenience.
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
if(n == 0) return true;
if(flowerbed.size() == 0) return false;
flowerbed.insert(flowerbed.begin(),0);
flowerbed.push_back(0);
for(int i=1; i<flowerbed.size()-1; i++) {
if(flowerbed[i-1] + flowerbed[i] + flowerbed[i+1] == 0) {
i++;
n--;
}
}
return n<=0;
}
Solution 2.
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
if(n == 0) return true;
if(flowerbed.size() == 0) return false;
int z = flowerbed[0] ? 0 : 2, res = 0; // a 0 at beginning counted as 2
for(int i=1; i<flowerbed.size(); i++) {
if(flowerbed[i] == 1 && flowerbed[i-1] == 0) {
res += (z-1)/2;
z = 0;
if(res>=n) return true;
}
else if(flowerbed[i] == 0 && flowerbed[i-1] == 1) {
z = 1;
}
else if(flowerbed[i] == 0) z++;
else continue;
}
res += z/2;
if(res>=n) return true;
return false;
}
Wednesday, August 30, 2017
645. Set Mismatch
https://leetcode.com/problems/set-mismatch/description/
Solution 0. Use XOR and count numbers
vector<int> findErrorNums(vector<int>& nums) {
vector<int> cnt(nums.size(),0);
vector<int> res = {0, 0};
for(int i=0; i<nums.size(); i++) {
if(++cnt[nums[i]-1] == 2)
res[0] = nums[i];
res[1] ^= (i+1)^nums[i];
}
res[1] ^= res[0];
return res;
}
Solution 1. Sort by putting nums[i] at index nums[i]-1
vector<int> findErrorNums(vector<int>& nums) {
for(int i=0; i<nums.size(); i++) {
while(nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
}
for(int i=0; i<nums.size(); i++) {
if(nums[i] != i+1) return {nums[i], i+1};
}
}
Solution 2. Use bitset
vector<int> findErrorNums(vector<int>& nums) {
bitset<10000> bits(0);
vector<int> res;
for(auto n: nums) {
if(bits.test(n-1)) res.push_back(n);
else bits.set(n-1);
}
for(int i=0; i<bits.size(); i++) {
if(!bits[i]) {
res.push_back(i+1);
break;
}
}
return res;
}
Solution 0. Use XOR and count numbers
vector<int> findErrorNums(vector<int>& nums) {
vector<int> cnt(nums.size(),0);
vector<int> res = {0, 0};
for(int i=0; i<nums.size(); i++) {
if(++cnt[nums[i]-1] == 2)
res[0] = nums[i];
res[1] ^= (i+1)^nums[i];
}
res[1] ^= res[0];
return res;
}
Solution 1. Sort by putting nums[i] at index nums[i]-1
vector<int> findErrorNums(vector<int>& nums) {
for(int i=0; i<nums.size(); i++) {
while(nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
}
for(int i=0; i<nums.size(); i++) {
if(nums[i] != i+1) return {nums[i], i+1};
}
}
Solution 2. Use bitset
vector<int> findErrorNums(vector<int>& nums) {
bitset<10000> bits(0);
vector<int> res;
for(auto n: nums) {
if(bits.test(n-1)) res.push_back(n);
else bits.set(n-1);
}
for(int i=0; i<bits.size(); i++) {
if(!bits[i]) {
res.push_back(i+1);
break;
}
}
return res;
}
Subscribe to:
Posts (Atom)