Related: LeetCode 260 - Single Number III
https://leetcode.com/problems/single-number-ii/
X. 32N
https://leetcode.com/problems/single-number-ii/discuss/43313/A-general-C%2B%2B-solution-for-these-type-problems
https://blog.csdn.net/qq508618087/article/details/50450165
分别计算到当前位置出现一次的数, 出现两次的数, 出现三次的数(用于消除出现在一次和二次的结果中出现三次的数). 其中出现一次的数很好统计, 只要异或就行, 这样最后保留的就是出现奇数次的数.
统计出现两次的数就要看这个数之前是不是出现过, 也就是和出现一次的数按位与就行了.
统计出现三次的数就要他是不是出现奇数次, 并且至少出现了两次.
这样当我们统计好这三个量之后还要消除在出现one中出现三次的数, two中出现三次的数. 这样在one和two中剩下就是只出现一次和两次的数
1. (ones ^ A[i])两个数异或是把两个数各自位上的1、0相减的绝对值。
ones表示历史迭代中各位上出现1的个数，当前A[i]与它异或：
> 每位上两者都是1的，表示历史统计结果ones出现1次、A[i]中又出现1次，则是2次。
> 每位上两者分别为0、1的，纳入ones统计结果。
2. & ~twos ---- 是为了出现3次后清0
&~twos表示与twos的非相与，什么意思呢？
(ones ^ A[i])表示历史统计到A[i]为止出现1的个数，假设 = 1100，此时twos=0100，表示在从右向左数第3位上，出现了1次，同时之前也出现了2次(在twos里），即出现了1+2=3次，对于3次的结果需滤除，所以对twos中出现过的，要&~。
https://medium.com/@lenchen/leetcode-137-single-number-ii-31af98b0f462
def singleNumber(self, nums):
# approach: by drawing truth table for 00 -> 01 -> 10 -> 00
# l' = ~h & (l ^ i)
# h' = ~l' & (h ^ i)
low_bits = high_bits = 0
for num in nums:
low_bits = ~high_bits & (low_bits ^ num)
high_bits = ~low_bits & (high_bits ^ num)
return low_bits
https://leetcode.com/problems/single-number-ii/discuss/43332/My-own-explanation-of-bit-manipulation-method-might-be-easier-to-understand
https://leetcode.com/problems/single-number-ii/discuss/43294/Challenge-me-thx
What's the value we should return?
If we operate the single number as the last number, then the ending state from previous operation is 00. If we do the same operation for the single number, state becomes 01, thus the result is in ones
http://www.cnblogs.com/grandyang/p/4263927.html
public int singleNumber2(int[] nums) {
// 只出现一次的掩码变量，
int ones = 0;
// 只出现两次次的掩码变量
int twos = 0;
// 只出现三次的掩码变量
int threes;
for (int n : nums) {
twos |= ones & n;
// 异或3次 和 异或 1次的结果是一样的
ones ^= n;
// 对于ones和twos把出现了3次的位置设置为0（取反之后1的位置为0）
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
https://leetcode.com/problems/single-number-ii/discuss/43403/java-bit-manipulation-solution
X. Generalization
https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers
http://www.cnblogs.com/daijinqiao/p/3352893.html
https://leetcode.com/problems/single-number-ii/
Given a non-empty 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?
Example 1:
Input: [2,2,3,2] Output: 3
Example 2:
Input: [0,1,0,1,0,1,99] Output: 99
X. 32N
https://leetcode.com/problems/single-number-ii/discuss/43313/A-general-C%2B%2B-solution-for-these-type-problems
Q: Most elements appeared k times, except one. Find this "one".
https://leetcode.com/problems/single-number-ii/discuss/43297/Java-O(n)-easy-to-understand-solution-easily-extended-to-any-times-of-occurance
I like to think about the number in 32 bits and just count how many 1s are there in each bit, and
sum %= 3 will clear it once it reaches 3. After running for all the numbers for each bit, if we have a 1, then that 1 belongs to the single number, we can simply move it back to its spot by doing ans |= sum << i;
This has complexity of O(32n), which is essentially O(n) and very easy to think and implement. Plus, you get a general solution for any times of occurrence. Say all the numbers have 5 times, just do
sum %= 5.public int singleNumber(int[] nums) {
int ans = 0;
for(int i = 0; i < 32; i++) {
int sum = 0;
for(int j = 0; j < nums.length; j++) {
if(((nums[j] >> i) & 1) == 1) {
sum++;
sum %= 3;
}
}
if(sum != 0) {
ans |= sum << i;
}
}
return ans;
}https://blog.csdn.net/qq508618087/article/details/50450165
分别计算到当前位置出现一次的数, 出现两次的数, 出现三次的数(用于消除出现在一次和二次的结果中出现三次的数). 其中出现一次的数很好统计, 只要异或就行, 这样最后保留的就是出现奇数次的数.
统计出现两次的数就要看这个数之前是不是出现过, 也就是和出现一次的数按位与就行了.
统计出现三次的数就要他是不是出现奇数次, 并且至少出现了两次.
这样当我们统计好这三个量之后还要消除在出现one中出现三次的数, two中出现三次的数. 这样在one和two中剩下就是只出现一次和两次的数
我们把数组中数字的每一位累加起来对3取余，剩下的结果就是那个单独数组该位上的数字，由于我们累加的过程都要对3取余，那么每一位上累加的过程就是0->1->2->0，换成二进制的表示为00->01->10->00，那么我们可以写出对应关系：
00 (+) 1 = 01
01 (+) 1 = 10
10 (+) 1 = 00 ( mod 3)
那么我们用ab来表示开始的状态，对于加1操作后，得到的新状态的ab的算法如下：
b = b xor r & ~a;
a = a xor r & ~b;
我们这里的ab就是上面的三种状态00，01，10的十位和各位，刚开始的时候，a和b都是0，当此时遇到数字1的时候，b更新为1，a更新为0，就是01的状态；再次遇到1的时候，b更新为0，a更新为1，就是10的状态；再次遇到1的时候，b更新为0，a更新为0，就是00的状态，相当于重置了；最后的结果保存在b中
int singleNumber(vector<int>& nums) { int a = 0, b = 0; for (int i = 0; i < nums.size(); ++i) { b = (b ^ nums[i]) & ~a; a = (a ^ nums[i]) & ~b; } return b; }https://blog.csdn.net/karen0310/article/details/78226261
1. (ones ^ A[i])两个数异或是把两个数各自位上的1、0相减的绝对值。
ones表示历史迭代中各位上出现1的个数，当前A[i]与它异或：
> 每位上两者都是1的，表示历史统计结果ones出现1次、A[i]中又出现1次，则是2次。
> 每位上两者分别为0、1的，纳入ones统计结果。
2. & ~twos ---- 是为了出现3次后清0
&~twos表示与twos的非相与，什么意思呢？
(ones ^ A[i])表示历史统计到A[i]为止出现1的个数，假设 = 1100，此时twos=0100，表示在从右向左数第3位上，出现了1次，同时之前也出现了2次(在twos里），即出现了1+2=3次，对于3次的结果需滤除，所以对twos中出现过的，要&~。
https://medium.com/@lenchen/leetcode-137-single-number-ii-31af98b0f462
Because there are all odd occurrence of all numbers, it can’t simply use XOR operator to extract the only one. Does that means we can’t use bit operation for this problem? The answer is NO. We can design the digital logic what we need so the only one can still be extracted.
Because every number will appear three times except only one, we need two bits to save the 3 states of all elements. Our goal is to design a logic operation that will be transformed by following this rule:
00 -> 01 -> 10 -> 00. Let’s assume the input is i , the low bit be l, the high bit be h, the new low bit be l’ and the new high bit be h’. We can draw the truth table of the 3 states as follow:h | l | i | h'| l' ------------------- 0 | 0 | 0 | 0 | 0 => no input, no change ------------------- 0 | 1 | 0 | 0 | 1 => no input, no change ------------------- 1 | 0 | 0 | 1 | 0 => no input, no change ------------------- 0 | 0 | 1 | 0 | 1 => 00 -> 01 ------------------- 0 | 1 | 1 | 1 | 0 => 01 -> 10 ------------------- 1 | 0 | 1 | 0 | 0 => 10 -> 00
By above truth table, we can compute
h' and l' by h , l and i:h' = h & ~l & ~i | ~h & l & i with third and fifth rows of truth tablel' = ~h & l & ~i | ~h & ~l & i with second and forth rows of truth table
And the later can further be reduced to:
l' = ~h & (l ^ i) — formula 1.
Moreover, if we let
l' be assigned first, h' can also be computed by l':h' = h & ~i & ~l' | ~h & i & ~l' with third and fifth rows of truth table
which is also equal to
h' = ~l' & (h ^ i) — formula 2.
By formula 1 and 2, we can easily extract the only single one by taking low bit, which means the number whose state still remains
01def singleNumber(self, nums):
# approach: by drawing truth table for 00 -> 01 -> 10 -> 00
# l' = ~h & (l ^ i)
# h' = ~l' & (h ^ i)
low_bits = high_bits = 0
for num in nums:
low_bits = ~high_bits & (low_bits ^ num)
high_bits = ~low_bits & (high_bits ^ num)
return low_bits
https://leetcode.com/problems/single-number-ii/discuss/43332/My-own-explanation-of-bit-manipulation-method-might-be-easier-to-understand
since counts % 3 has only 3 states: 0(00),1(01),2(10)
we could use a TWO BIT COUNTER (Two, One) to represent Counts % 3, now we could do a little research on state transitions, for each bit, let B be the input bit, we can enumerate the all possible state transitions, Two+, One+ is the new state of Two, One. (here we need to use some knowledge in Digital Logic Design)
we could use a TWO BIT COUNTER (Two, One) to represent Counts % 3, now we could do a little research on state transitions, for each bit, let B be the input bit, we can enumerate the all possible state transitions, Two+, One+ is the new state of Two, One. (here we need to use some knowledge in Digital Logic Design)
Two One B Two+ One+0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 1 01 0 1 0 01 1 0 X X (X represents we don't care)1 1 1 X X
We could then draw the Karnaugh map to analyze the logic (https://en.wikipedia.org/wiki/Karnaugh_map), and then we get:
One+ = (One ^ B) & (~Two)Two+ = (~One+) & (Two ^ B)
Now for int_32, we need only 2 int_32 two represent Two and One for each bit and update Two and One using the rules derived above
int singleNumber(vector<int>& nums) {
int counterOne = 0;
int counterTwo = 0;
for (int i = 0; i < nums.size(); i++){
counterOne = (~counterTwo) & (counterOne ^ nums[i]);
counterTwo = (~counterOne) & (counterTwo ^ nums[i]);
}
return counterOne;
} 如果是出现两次的话，用一个bit就可以
比如 b，初始为0
当5第1次出现时， b=5
当5第2次出现是， b清空为0，表示b可以去处理其他数字了
所以，最后 如果 b !=0的话，b记录的就是只出现了一次的那个数字
->公式就是 b = b xor i 或者 b = b^i
那么，如果是三次的话，香浓定理，需要用2bits进行记录
当5第一次出现的时候，b = 5, a=0, b记录这个数字
当5第二次出现的时候，b = 0, a=5， a记录了这个数字
当5第三次出现的时候，b = 0, a=0， 都清空了，可以去处理其他数字了
所以，如果有某个数字出现了1次，就存在b中，出现了两次，就存在a中，所以返回 a|b
公式方面 ，上面两次的时候，b清空的公式是 b = b xor i
而第三次时，b要等于零，而这时a是True，所以再 & 一个a的非就可以，b = b xor & ~a
-> b = b xor i & ~ a
a = a xor i & ~b
a = b = 0
for num in nums:
b = b ^ num & ~a
a = a ^ num & ~b
return a|b
What's the value we should return?
If we operate the single number as the last number, then the ending state from previous operation is 00. If we do the same operation for the single number, state becomes 01, thus the result is in ones
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;
}http://www.cnblogs.com/grandyang/p/4263927.html
用3个整数来表示INT的各位的出现次数情况，one表示出现了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。
ones代表第ith 位只出现一次的掩码变量twos代表第ith 位只出现两次次的掩码变量threes代表第ith 位只出现三次的掩码变量
假设现在有一个数字1，那么我们更新one的方法就是‘亦或’这个1，则one就变成了1.
而two的更新方法是用上一个状态下的one去‘与’上数字1，然后‘或’上这个结果，这样假如之前one是1，那么此时two也会变成1，这make sense，因为说明是当前位遇到两个1了；反之如果之前one是0，那么现在two也就是0。
注意更新的顺序是先更新two，再更新one，不理解的话只要带个只有一个数字1的输入数组看一下就不难理解了。
然后我们更新three，如果此时one和two都是1了，那么由于我们先更新的two，再更新的one，two为1，说明此时至少有两个数字1了，而此时one为1，说明了此时已经有了三个数字1，这块要仔细想清楚，因为one是要‘亦或’一个1的，值能为1，说明之前one为0，实际情况是，当第二个1来的时候，two先更新为1，此时one再更新为0，下面three就是0了，那么‘与’上three的相反数1不会改变one和two的值；那么当第三个1来的时候，two还是1，此时one就更新为1了，那么three就更新为1了，此时就要清空one和two了，让它们‘与’上three的相反数0即可，最终结果将会保存在one中
int singleNumber(vector<int>& nums) { int one = 0, two = 0, three = 0; for (int i = 0; i < nums.size(); ++i) { two |= one & nums[i]; one ^= nums[i]; three = one & two; one &= ~three; two &= ~three; } return one; }https://blog.csdn.net/DERRANTCM/article/details/47745445
public int singleNumber2(int[] nums) {
// 只出现一次的掩码变量，
int ones = 0;
// 只出现两次次的掩码变量
int twos = 0;
// 只出现三次的掩码变量
int threes;
for (int n : nums) {
twos |= ones & n;
// 异或3次 和 异或 1次的结果是一样的
ones ^= n;
// 对于ones和twos把出现了3次的位置设置为0（取反之后1的位置为0）
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
https://leetcode.com/problems/single-number-ii/discuss/43403/java-bit-manipulation-solution
public int singleNumber(int[] nums) {
int ones = 0, twos = 0, threes = 0;
for (int i = 0; i < nums.length; i++) {
// twos holds the num that appears twice
twos |= ones & nums[i];
// ones holds the num that appears once
ones ^= nums[i];
// threes holds the num that appears three times
threes = ones & twos;
// if num[i] appears three times
// doing this will clear ones and twos
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
The code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.
So if at any point time,
- A new number appears - It gets XOR'd to the variable "ones".
- A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twos". - A number appears for the third time - It gets removed from both "ones" and "twos".
The final answer we want is the value present in "ones" - coz, it holds the unique element.
So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,
Before explaining above 3 steps, lets look at last three lines of the code,
common_bit_mask = ~(ones & twos)
ones & = common_bit_mask
twos & = common_bit_mask
All it does is, common 1's between "ones" and "twos" are converted to zero.
For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).
Explanation for step 1
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".
Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".
The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.
Explanation for step 2.
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".
Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.
Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".
Explanation for step 3.
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.
Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".
Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".
public:
// Let us take the example of {3, 3, 2, 3} to understand this
int singleNumber(int A[], int n) {
int ones=0, twos =0;
int common_bit_mask;
for(int i=0; i<n;i++)
{
/* The expression "one & arr[i]" gives the bits that are
there in both 'ones' and new element from arr[]. We
add these bits to 'twos' using bitwise OR
Value of 'twos' will be set as 0, 3, 3 and 1 after 1st,
2nd, 3rd and 4th iterations respectively */
twos= twos|(ones&A[i]);
/* XOR the new bits with previous 'ones' to get all bits
appearing odd number of times
Value of 'ones' will be set as 3, 0, 2 and 3 after 1st,
2nd, 3rd and 4th iterations respectively */
ones=ones^A[i];
/* The common bits are those bits which appear third time
So these bits should not be there in both 'ones' and 'twos'.
common_bit_mask contains all these bits as 0, so that the bits can
be removed from 'ones' and 'twos'
Value of 'common_bit_mask' will be set as 00, 00, 01 and 10
after 1st, 2nd, 3rd and 4th iterations respectively */
common_bit_mask= ~(ones&twos);
/* Remove common bits (the bits that appear third time) from 'ones'
Value of 'ones' will be set as 3, 0, 0 and 2 after 1st,
2nd, 3rd and 4th iterations respectively */
ones &=common_bit_mask;
/* Remove common bits (the bits that appear third time) from 'twos'
Value of 'twos' will be set as 0, 3, 1 and 0 after 1st,
2nd, 3rd and 4th itearations respectively */
twos &=common_bit_mask;
}
return ones;
}
X. Generalization
https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers
I -- Statement of our problem
"Given an array of integers, every element appears
k (k > 1) times except for one, which appears p times (p >= 1, p % k != 0). Find that single one."II -- Special case with 1-bit numbers
As others pointed out, in order to apply the bitwise operations, we should rethink how integers are represented in computers -- by bits. To start, let's consider only one bit for now. Suppose we have an array of 1-bit numbers (which can only be
0 or 1), we'd like to count the number of 1's in the array such that whenever the counted number of 1 reaches a certain value, say k, the count returns to zero and starts over (in case you are curious, this k will be the same as the one in the problem statement above). To keep track of how many 1's we have encountered so far, we need a counter. Suppose the counter has m bits in binary form: xm, ..., x1 (from most significant bit to least significant bit). We can conclude at least the following four properties of the counter:- There is an initial state of the counter, which for simplicity is zero;
- For each input from the array, if we hit a
0, the counter should remain unchanged; - For each input from the array, if we hit a
1, the counter should increase by one; - In order to cover
kcounts, we require2^m >= k, which impliesm >= logk.
Here is the key part: how each bit in the counter (
x1 to xm) changes as we are scanning the array. Note we are prompted to use bitwise operations. In order to satisfy the second property, recall what bitwise operations will not change the operand if the other operand is 0? Yes, you got it: x = x | 0 and x = x ^ 0.
Okay, we have an expression now:
x = x | i or x = x ^ i, where i is the scanned element from the array. Which one is better? We don't know yet. So, let's just do the actual counting.
At the beginning, all bits of the counter is initialized to zero, i.e.,
xm = 0, ..., x1 = 0. Since we are gonna choose bitwise operations that guarantee all bits of the counter remain unchanged if we hit 0's, the counter will be 0 until we hit the first 1 in the array. After we hit the first 1, we got: xm = 0, ...,x2 = 0, x1 = 1. Let's continue until we hit the second 1, after which we have: xm = 0, ..., x2 = 1, x1 = 0. Note that x1 changed from 1 to 0. For x1 = x1 | i, after the second count, x1 will still be 1. So it's clear we should use x1 = x1 ^ i. What about x2, ..., xm? The idea is to find the condition under which x2, ..., xm will change their values. Take x2 as an example. If we hit a 1 and need to change the value of x2, what must be the value of x1 right before we do the change? The answer is: x1 must be 1 otherwise we shouldn't change x2 because changing x1 from 0 to 1 will do the job. So x2 will change value only if x1 and i are both 1, or mathematically, x2 = x2 ^ (x1 & i). Similarly xm will change value only when xm-1, ..., x1 and i are all 1: xm = xm ^ (xm-1 & ... & x1 & i). Bingo, we've found the bitwise operations!
However, you may notice that the bitwise operations found above will count from
0 until 2^m - 1, instead of k. If k < 2^m - 1, we need some "cutting" mechanism to reinitialize the counter to 0 when the count reaches k. To this end, we apply bitwise AND to xm,..., x1 with some variable called mask, i.e., xm = xm & mask, ..., x1 = x1 & mask. If we can make sure that mask will be 0 only when the count reaches k and be 1 for all other count cases, then we are done. How do we achieve that? Try to think what distinguishes the case with k count from all other count cases. Yes, it's the count of 1's! For each count, we have unique values for each bit of the counter, which can be regarded as its state. If we write k in its binary form: km,..., k1, we can construct mask as follows:mask = ~(y1 & y2 & ... & ym), where yj = xj if kj = 1, and yj = ~xj if kj = 0 (j = 1 to m).
Let's do some examples:
k = 3: k1 = 1, k2 = 1, mask = ~(x1 & x2);k = 5: k1 = 1, k2 = 0, k3 = 1, mask = ~(x1 & ~x2 & x3);
In summary, our algorithm will go like this (
nums is the input array):for (int i : nums) {
xm ^= (xm-1 & ... & x1 & i);
xm-1 ^= (xm-2 & ... & x1 & i);
.....
x1 ^= i;
mask = ~(y1 & y2 & ... & ym) where yj = xj if kj = 1, and yj = ~xj if kj = 0 (j = 1 to m).
xm &= mask;
......
x1 &= mask;
}
III -- General case with 32-bit numbers
Now it's time to generalize our results from 1-bit number case to 32-bit integers. One straightforward way would be creating
32 counters for each bit in the integer. You've probably already seen this in other posted solutions. However, if we take advantage of bitwise operations, we may be able to manage all the 32 counters "collectively". By saying "collectively", we mean using m 32-bit integers instead of 32 m-bit counters, where m is the minimum integer that satisfies m >= logk. The reason is that bitwise operations apply only to each bit so operations on different bits are independent of each other (kind obvious, right?). This allows us to group the corresponding bits of the 32 counters into one 32-bit integer. Here is a schematic diagram showing how this is done.
The top row is the 32-bit integer, where for each bit, we have a corresponding m-bit counter (shown by the column below the upward arrow). Since bitwise operations on each of the
32 bits are independent of each other, we can group, say the m-th bit of all counters, into one 32-bit number (shown by the orange box). All bits in this 32-bit number (denoted as xm) will follow the same bitwise operations. Since each counter has m bits, we end up with m 32-bit numbers, which correspond to x1, ..., xm defined in part II, but now they are 32-bit integers instead of 1-bit numbers. Therefore, in the algorithm developed above, we just need to regard x1 to xm as 32-bit integers instead of 1-bit numbers. Everything else will be the same and we are done. Easy, hum?IV -- What to return
The last thing is what value we should return, or equivalently which one of
x1 to xm will equal the single element. To get the correct answer, we need to understand what the m 32-bit integers x1 to xm represent. Take x1 as an example. x1 has 32 bits and let's label them as r (r = 1 to 32). After we are done scanning the input array, the value for the r-th bit of x1 will be determined by the r-th bit of all the elements in the array (more specifically, suppose the total count of 1 for the r-th bit of all the elements in the array is q, q' = q % k and in its binary form: q'm,...,q'1, then by definition the r-th bit of x1 will be equal to q'1). Now you can ask yourself this question: what does it imply if the r-th bit of x1 is 1?
The answer is to find what can contribute to this
1. Will an element that appears k times contribute? No. Why? Because for an element to contribute, it has to satisfy at least two conditions at the same time: the r-th bit of this element is 1 and the number of appearance of this 1 is not an integer multiple of k. The first condition is trivial. The second comes from the fact that whenever the number of 1 hit is k, the counter will go back to zero, which means the corresponding bit in x1 will be reset to 0. For an element that appears k times, it's impossible to meet these two conditions simultaneously so it won't contribute. At last, only the single element which appears p (p % k != 0) times will contribute. If p > k, then the first k * [p/k] ([p/k]denotes the integer part of p/k) single elements won't contribute either. So we can always set p' = p % k and say the single element appears effectively p' times.
Let's write
p' in its binary form: p'm, ..., p'1 (note that p' < k, so it will fit into m bits). Here I claim the condition for xj to equal the single element is p'j = 1 (j = 1 to m), with a quick proof given below.
If the
r-th bit of xj is 1, we can safely say the r-th bit of the single element is also 1 (otherwise nothing can make the r-th bit of xj to be 1). We are left to prove that if the r-th bit of xj is 0, then the r-th bit of the single element can only be 0. Just suppose in this case the r-th bit of the single element is 1, let's see what will happen. At the end of the scan, this 1 will be counted p' times. By definition the r-th bit of xj will be equal to p'j, which is 1. This contradicts with the presumption that the r-th bit of xj is 0. Therefore we conclude the r-th bit of xj will always be the same as the r-th bit of the single number as long as p'j = 1. Since this is true for all bits in xj (i.e., true for r = 1 to 32), we conclude xj will equal the single element as long as p'j = 1.
So now it's clear what we should return. Just express
p' = p % k in its binary form and return any of the corresponding xj as long as p'j = 1. In total, the algorithm will run in O(n * logk) time and O(logk) space.
Side note: There is a general formula relating each bit of
xj to p'j and each bit of the single number s, which is given by (xj)_r = s_r & p'j, with (xj)_r and s_r denoting respectively the r-th bit of xj and the single number s. From this formula, it's easy to see that (xj)_r = s_r if p'j = 1, that is, xj = s as long as p'j = 1, as shown above. Furthermore, we have (xj)_r = 0 if p'j = 0, regardless of the value of the single number, that is, xj = 0 as long as p'j = 0. So in summary we obtain: xj = s if p'j = 1, and xj = 0 if p'j = 0. This implies the expression (x1 | x2 | ... | xm) will also be evaluated to the single number s, since the expression will essentially take the OR operations of the single number with itself and some 0s, which boils down to the single number eventually.V -- Quick examples
Here is a list of few quick examples to show how the algorithm works (you can easily come up with other examples):
k = 2, p = 1kis2, thenm = 1, we need only one 32-bit integer (x1) as the counter. And2^m = kso we do not even need a mask! A complete java program will look like:
public int singleNumber(int[] nums) {
int x1 = 0;
for (int i : nums) {
x1 ^= i;
}
return x1;
}
k = 3, p = 1kis3, thenm = 2, we need two 32-bit integers(x2,x1) as the counter. And2^m > kso we do need a mask. Writekin its binary form:k = '11', thenk1 = 1,k2 = 1, so we havemask = ~(x1 & x2). A complete java program will look like:
public int singleNumber(int[] nums) {
int x1 = 0, x2 = 0, mask = 0;
for (int i : nums) {
x2 ^= x1 & i;
x1 ^= i;
mask = ~(x1 & x2);
x2 &= mask;
x1 &= mask;
}
return x1; // Since p = 1, in binary form p = '01', then p1 = 1, so we should return x1.
// If p = 2, in binary form p = '10', then p2 = 1, and we should return x2.
// Or alternatively we can simply return (x1 | x2).
}
k = 5, p = 3kis5, thenm = 3, we need three 32-bit integers(x3,x2,x1) as the counter. And2^m > kso we need a mask. Writekin its binary form:k = '101', thenk1 = 1,k2 = 0,k3 = 1, so we havemask = ~(x1 & ~x2 & x3). A complete java program will look like:
public int singleNumber(int[] nums) {
int x1 = 0, x2 = 0, x3 = 0, mask = 0;
for (int i : nums) {
x3 ^= x2 & x1 & i;
x2 ^= x1 & i;
x1 ^= i;
mask = ~(x1 & ~x2 & x3);
x3 &= mask;
x2 &= mask;
x1 &= mask;
}
return x1; // Since p = 3, in binary form p = '011', then p1 = p2 = 1, so we can return either x1 or x2.
// If p = 4, in binary form p = '100', only p3 = 1, which implies we can only return x3.
// Or alternatively we can simply return (x1 | x2 | x3).
}http://www.cnblogs.com/daijinqiao/p/3352893.html
给定一个包含n个整数的数组，除了一个数出现二次外所有的整数均出现三次，找出这个只出现二次的整数。ones记录1出现一次的数，twos记录1出现2次的数，容易知道twos记录的即是最终结果。
扩展二：
给定一个包含n个整数的数组，有一个整数x出现b次，一个整数y出现c次，其他所有的数均出现a次，其中b和c均不是a的倍数，找出x和y。使用二进制模拟a进制，累计二进制位1出现的次数，当次数达到a时，对其清零，这样可以得到b mod a次x，c mod a次y的累加。遍历剩余结果（用ones、twos、fours...变量表示）中每一位二进制位1出现的次数，如果次数为b mod a 或者 c mod a，可以说明x和y的当前二进制位不同（一个为0，另一个为1），据此二进制位将原数组分成两组，一组该二进制位为1，另一组该二进制位为0。这样问题变成“除了一个整数出现a1次（a1 = b 或 a1 = c）外所有的整数均出现a次”，使用和上面相同的方式计算就可以得到最终结果，假设模拟a进制计算过程中使用的变量为ones、twos、fours...那么最终结果可以用ones | twos | fours ...表示。
http://www.voidcn.com/article/p-rxjthzra-bcx.html public int singleNumber(int[] nums) {
Arrays.sort(nums);
int number = 0;
boolean flag = true;
for(int i = 0 ; i<nums.length-2 ; i++){
if(nums[i] == nums[i+1] && nums[i+1] == nums[i+2]){
i+=2;
}else{
if(nums[i]==nums[i+1]){
number = i + 2;
}else{
number = i;
}
flag=false;
break;
}
}
if(flag){
number = nums.length-1;
}
return nums[number];
}
