Problem statement
Elementary knowledge:
There is a popular question when I seeked my job at Beijing: swap the value of two numbers without allocate a new memory.
Normally, there are two solutions:
1 int main(){
2 int a = 3;
3 int b = 5;
4
5 a += b;
6 b = a - b;
7 a = a - b;
8
9 a ^= b;
10 b ^= a;
11 a ^= b;
12
13 return 0;
14 }
Some tricky:
x&(x-1): eliminate the last 1 bit in x
We can use this tricky to test if an integer is the power of 2 in O(1) time;
class Solution {
public:
/*
* @param n: An integer
* @return: True or false
*/
bool checkPowerOf2(int n) {
// write your code here
return n > && (n & (n - )) == ;
}
};
Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Solution one:
For this problem, we should use the knowledge that the XOR operation for two same number will be zero.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int single_val = ;
for(vector<int>::size_type ix = ; ix < nums.size(); ix++){
single_val ^= nums[ix];
}
return single_val;
}
};
Solution two:
Since the array is random, the first action is to sort the array from small to large.
I keep a counter to count the number of current value. The loop ends at the element before the last one since we will compare current element with it`s direct next one. Because of this, we need do some boundary check to make sure there is at least one element in this array
- if they are equal, the counter + 1;
- if they are not equal:
- if the counter is 2, that means current is already end in the array, we need precede to it`s next one, the counter should start from 1 again.
- if the counter is less than 2( it should be 1), that means current only show up once, it is the single we want. return;
- If the function does not return in the while loop, that means the last element is the single value, we return nums.back();
class Solution {
public:
int singleNumber(vector<int>& nums) {
if(nums.empty()){
return ;
}
if(nums.size() == ){
return nums[];
}
sort(nums.begin(), nums.end());
int cnt = ;
for(vector<int>::size_type ix = ; ix < nums.size() - ; ix++){
if(nums[ix] == nums[ix + ]){
cnt++;
} else {
if(cnt < ){
return nums[ix];
} else {
cnt = ;
}
}
}
return nums.back();
}
};
Single Number ii
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Solution one:
Frist solutiuon is the same with singlue number i, we just need change the value of cnt to be 3, it will works.
class Solution {
public:
int singleNumber(vector<int>& nums) {
if (nums.size() == ) {
return nums[];
}
sort(nums.begin(), nums.end());
int cnt = ;
for (vector<int>::size_type ix = ; ix < nums.size(); ix++) {
if (nums[ix] == nums[ix + ]) {
cnt++;
} else {
if (cnt < ) {
return nums[ix];
} else {
cnt = ;
}
}
}
return nums.back();
}
};
Solution two:
- For each integer, it is represented by 32 bits, we count the number of "1"s for each i
- Do "module 3" operation and "or" operation to put it back to the result.
- Except the single value, other values occur three time, that means the bit should be zero if the count is moduled with 3.
- We will get the value of single number.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int single_val = ;
int bit_sum = ;
for(int i = ; i < ; i++){
bit_sum = ;
for(vector<int>::size_type ix = ; ix < nums.size(); ix++){
bit_sum += (nums[ix] >> i) & ;
}
single_val |= (bit_sum % ) << i;
}
return single_val;
}
};
Solution three:
- ones: means the value when ith bit only occurs once
- twos: means the value when ith bit only occurs twice
- three: measn the value when ith bit only occurs third
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = , two = , three = ;
for (int i = ; i < nums.size(); ++i) {
two |= one & nums[i];
one ^= nums[i];
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
};
Single number iii
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
The rules for xor operation:
0: two bits are same
1: two bits are different
The xor operation is similiar with an addition without carry.
Solution:
There are two numbers only occur once, which is different with single number i. We can solve it with the single number i, however, we need do some precess before it.
- First, we do xor operations for all element in the array, the result is the xor of two number we want.
- Second, we should find one bit which is different in these two numbers and use this bit as an indicator to different them in next loop
- The bit representation of a negative number is: reverse all bits of its positive number and plus one
- Third, loop all elements in array to do xor operation and get the answer.
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int xor_of_two_numbers = ;
for(vector<int>::size_type ix = ; ix < nums.size(); ix++){
// this is the result of the xor of two single numbers
xor_of_two_numbers ^= nums[ix];
}
// the negative bit representation of each number
// reverse all bits and plus one
// find one bit from the xor result which this two single numbers is different
// different them in next loop
int right_most_bit_of_xor = xor_of_two_numbers & -xor_of_two_numbers;
vector<int> singleNumber();
for(vector<int>::size_type ix = ; ix < nums.size(); ix++){
if(nums[ix] & right_most_bit_of_xor){
singleNumber[] ^= nums[ix];
} else {
singleNumber[] ^= nums[ix];
}
}
return singleNumber;
}
};