SingleNumberII [source code]
public class SingleNumberII {
static
/******************************************************************************/
class Solution {
public int singleNumber(int[] nums) {
return singleNumber (nums, 3);
}
public int singleNumber(int[] nums, int _K) {
int K = _K - 1;
int[] bits = new int[K];
for (int num : nums) {
for (int i = 0; i < K; i++) {
int mask = -1;
for (int j = 0; j < K; j++) if (j != i)
mask &= ~bits[j];
bits[i] = (bits[i] ^ num) & mask;
}
}
return bits[0];
}
}
/******************************************************************************/
public static void main(String[] args) {
SingleNumberII.Solution tester = new SingleNumberII.Solution();
int[] inputs = {
3,
4,
5,
};
for (int K : inputs) {
System.out.println (Printer.separator ());
int[] nums = new int[3 * K + 1];
nums[nums.length - 1] = 4;
for (int i = 0; i < 3; i++) for (int j = 0; j < K; j++)
nums[i * K + j] = i + 1;
int ans = 4, output = tester.singleNumber (nums, K);
System.out.printf ("%s -> %s, expected: %d\n",
Printer.array (nums), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
int[][] inputs2 = {
{2,2,2,3}, {3},
};
for (int i = 0; i < inputs2.length / 2; i++) {
System.out.println (Printer.separator ());
int[] nums = inputs2[2 * i];
int ans = inputs2[2 * i + 1][0], output = tester.singleNumber (nums);
System.out.printf ("%s -> %s, expected: %d\n",
Printer.array (nums), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
刷题刷到我现在这个阶段, 全新的套路出现的概率实际上不高了, 所以碰到新题目, 尤其是这个明显是跟以前的题目有关联的题目, 可以尝试是不是从已知题目的思路当中获得启发, 也就是跟熟悉的题目进行类比;
What's the naive way? What's the previous way? Can any adapatation be done?
O(1) space? in place flag? recursion?
大概想了一下, 感觉是脑筋急转弯之类的题目, 不浪费时间了, 直接看答案;
没有editorial;
https://leetcode.com/problems/single-number-ii/discuss/43294/Challenge-me-thx
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;
}
完全看不懂;
The code seems tricky and hard to understand at first glance.
However, if you consider the problem in Boolean algebra form, everything becomes clear.
What we need to do is to store the number of '1’s of every bit. Since each of the 32 bits follow the same rules, we just need to consider 1 bit. We know a number appears 3 times at most, so we need 2 bits to store that. Now we have 4 state, 00, 01, 10 and 11, but we only need 3 of them.
In this solution, 00, 01 and 10 are chosen. Let ‘ones’ represents the first bit, ‘twos’ represents the second bit. Then we need to set rules for ‘ones’ and ‘twos’ so that they act as we hopes. The complete loop is 00->10->01->00(0->1->2->3/0).
- For ‘ones’, we can get ‘ones = ones ^ A[i]; if (twos == 1) then ones = 0’, that can be tansformed to ‘ones = (ones ^ A[i]) & ~twos’.
- Similarly, for ‘twos’, we can get ‘twos = twos ^ A[i]; if (ones == 1) then twos = 0’ and ‘twos = (twos ^ A[i]) & ~ones’. Notice that ‘ones’ is the value of ‘ones’ after calculation, that is why twos is calculated later.
Here is another example. If a number appears 5 times at most, we can write a program using the same method. Now we need 3 bits and the loop is 000->100->010->110->001. The code looks like this:
int singleNumber(int A[], int n) {
int na = 0, nb = 0, nc = 0;
for(int i = 0; i < n; i++){
nb = nb ^ (A[i] & na);
na = (na ^ A[i]) & ~nc;
nc = nc ^ (A[i] & ~na & ~nb);
}
return na & ~nb & ~nc;
}
Or even like this:
int singleNumber(int A[], int n) {
int twos = 0xffffffff, threes = 0xffffffff, ones = 0;
for(int i = 0; i < n; i++){
threes = threes ^ (A[i] & twos);
twos = (twos ^ A[i]) & ~ones;
ones = ones ^ (A[i] & ~twos & ~threes);
}
return ones;
}
I hope all these above can help you have a better understand of this problem.
还是不太理解, 打一个trace:
Your input
[1,2,3,1,2,3,1,2,3,4]
Your stdout
i:(0), num:(1), twos:(0), ones:(1)
i:(1), num:(2), twos:(0), ones:(3)
i:(2), num:(3), twos:(3), ones:(0)
i:(3), num:(1), twos:(2), ones:(0)
i:(4), num:(2), twos:(0), ones:(0)
i:(5), num:(3), twos:(0), ones:(3)
i:(6), num:(1), twos:(1), ones:(2)
i:(7), num:(2), twos:(3), ones:(0)
i:(8), num:(3), twos:(0), ones:(0)
i:(9), num:(4), twos:(0), ones:(4)
是iteration结束之后的state;
换了一个方式打trace:
Your input
[1,2,3,1,2,3,1,2,3,4]
Your stdout
i:(0) >>> num: 1 twos: 0 ones: 1
i:(1) >>> num: 10 twos: 0 ones: 11
i:(2) >>> num: 11 twos: 11 ones: 0
i:(3) >>> num: 1 twos: 10 ones: 0
i:(4) >>> num: 10 twos: 0 ones: 0
i:(5) >>> num: 11 twos: 0 ones: 11
i:(6) >>> num: 1 twos: 1 ones: 10
i:(7) >>> num: 10 twos: 11 ones: 0
i:(8) >>> num: 11 twos: 0 ones: 0
i:(9) >>> num: 100 twos: 0 ones: 100
这个看的大概就是比较清楚了. 上面那个解释总体的意思是对的, 但是有一点你自己要理解;
上面那个人总体的思路是对的, 但是首先, 他对于循环说错了, 这里原来的作者设计的循环实际上是: 00->01->10->00: 自己对着某一个bit看, 就知道是不是这么一回事;
虽然实际上代码里面是对数字之间进行xor和各种bit运算, 但是实际上最后真正有效的运算都是进行在独立的bit上面的; 比如你看左边的num的bit0位置上的时候, 然后对应的twos和ones的bit0的位置, 你就知道什么意思了;
讲起来可能有点费劲, 关键就是一个bit一个bit的分开理解: 这个是bit操作的一个重要性质, bit之间是互相独立的, 所以虽然看起来是int之间的各种xor之类的操作, 实际上最后操作的本质还是分开parallel进行的各个bit的计算;
我把代码改成了这样:
class Solution {
public int singleNumber(int[] A) {
int[] bit_counts = new int[8];
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
updateBitCount (bit_counts, A[i]);
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
System.out.println (countsToString (bit_counts, twos, ones) + "\n");
}
return ones;
}
void updateBitCount (int[] bit_counts, int num) {
for (int i = 0; i < 8; i++) {
if ((num & (1 << i)) > 0)
bit_counts[i]++;
}
}
String countsToString (int[] bit_counts, int twos, int ones) {
StringBuilder sb1 = new StringBuilder ("bit counts:\t"), sb2 = new StringBuilder ("twos:\t\t"), sb3 = new StringBuilder ("ones:\t\t");
for (int i = 7; i >= 0; i--) {
sb1.append (String.format ("%3d ", bit_counts[i]));
sb2.append (String.format ("%3d ", (twos >> i) & 1));
sb3.append (String.format ("%3d ", (ones >> i) & 1));
}
return sb1.toString () + "\n" + sb2.toString () + "\n" + sb3.toString ();
}
}
然后一个trace:
Your input
[1,2,3,1,2,3,1,2,3,4]
Your stdout
bit counts: 0 0 0 0 0 0 0 1
twos: 0 0 0 0 0 0 0 0
ones: 0 0 0 0 0 0 0 1
bit counts: 0 0 0 0 0 0 1 1
twos: 0 0 0 0 0 0 0 0
ones: 0 0 0 0 0 0 1 1
bit counts: 0 0 0 0 0 0 2 2
twos: 0 0 0 0 0 0 1 1
ones: 0 0 0 0 0 0 0 0
bit counts: 0 0 0 0 0 0 2 3
twos: 0 0 0 0 0 0 1 0
ones: 0 0 0 0 0 0 0 0
bit counts: 0 0 0 0 0 0 3 3
twos: 0 0 0 0 0 0 0 0
ones: 0 0 0 0 0 0 0 0
bit counts: 0 0 0 0 0 0 4 4
twos: 0 0 0 0 0 0 0 0
ones: 0 0 0 0 0 0 1 1
bit counts: 0 0 0 0 0 0 4 5
twos: 0 0 0 0 0 0 0 1
ones: 0 0 0 0 0 0 1 0
bit counts: 0 0 0 0 0 0 5 5
twos: 0 0 0 0 0 0 1 1
ones: 0 0 0 0 0 0 0 0
bit counts: 0 0 0 0 0 0 6 6
twos: 0 0 0 0 0 0 0 0
ones: 0 0 0 0 0 0 0 0
bit counts: 0 0 0 0 0 1 6 6
twos: 0 0 0 0 0 0 0 0
ones: 0 0 0 0 0 1 0 0
这个应该就很清晰了, 可以很清楚的看到00->01->10->00这样一个循环;
剩下来要理解的, 就是怎样设计这样一个循环; 这里, 你就当做一个bit一个bit的操作就行了, 也就是你就把ones和twos看成两个bit, 然后你怎么设计;
他这里:
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
的逻辑确实有点复杂, 实际上, 如果只是为了设计这样一个循环, 并不需要这么复杂; 但是你可以declarative的理解一下他这里的代码: 这里实际上不要用clear mask的思路来理解, 并不是一回事;
这里正确的理解方式, 实际上是他保证ones和twos这两个bit不可能同时为1, 这个实际上也就是把00->01->10->11这个本来的加法循环(xor就是加法)当中的最后一环给去掉了; 总共两个bit, 总共可以有4个state, 你去掉了11这个state, 最后只剩下3个state, 正好就是我们需要的循环长度;
另外一个更加直接的做法:
class Solution {
public:
int singleNumber(int arr[], int n) {
// Initialize result
int result = 0;
int x, sum;
// Iterate through every bit
for (int i = 0; i < 32; i++)
{
// Find sum of set bits at ith position in all
// array elements
sum = 0;
x = (1 << i);
for (int j=0; j< n; j++ )
{
if (arr[j] & x)
sum++;
}
// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if (sum % 3)
result |= x;
}
return result;
}
};
严格来说这个做法是O(1) space, 但是你仔细看题目: 题目要求的实际上是without extra space, 所以这个做法实际上最后是有可能被喷的; 不过老实说OP自己的代码也用了两个int, 这个怎么说? 所以估计最后的要求应该就是O(1) space就行了;
Beautiful. Let me describe it to see if I’m understanding it right:
First time number appear -> save it in “ones”
Second time -> clear “ones” but save it in “twos” for later check
Third time -> try to save in “ones” but value saved in “twos” clear it.
这个解释有点太ad-hoc了, 不够general; 当然, general的角度去设计这么一个循环, 实际上并没有那么简单;
最general的方法你知道是什么吗? 在每一个i的位置, 直接把对应的bit都提取出来, 然后按照这个循环的path来改变state? 但是这样就要进行32次, 一次一个bit, 这个就麻烦了一点; bit的做法的优点是, 全部统一在一次的bit运算当中, 缺点就是这个逻辑并不是那么好设置;
Let me try to explain it more clearly:
X=***1***1*** Z=***0***0*** X=***1***1*** Y=***0***1*** X=***1***1*** Z=***0***0*** Z=***0***0*** P QX,Y,Z are 3 numbers and I show you the bit of them at position P, Q.
If you can count the bit sum of words for each bit position, its really the part sum % 3 that matters. If the one special word appear only once, then it can be directy got from sum % 3 for that bit.
For example,
you add all bits at Q you get 4 % 3 = 1, you get bit of Y at Q.
you add all bits at P you get 3 % 3 = 0, you get bit of Y at P.
So you are counting the sum, does the sequence of word matters? No. Because we only care about the sum, and especially the part of sum % 3. There’s a solution that achieves that you can check here: By rajan.buha, https://leetcode.com/discuss/6632/challenge-me-thx
When you add bit of each position, take a closer look at sum, whenever it is added by a 1, it changes to 0->1->2->0 … as a loop. In binary, it becomes 00->01->10->00.
Can I mimic the loop of each bit? Why do I do that? Later I will tell you.
Lets try to do that by designing bit operations,:
Suppose b1 and b0 are binary bit representing the sum:
I want to designso that when b1b0 adds a ‘1’, it has the table of 00 <add> 1 = 01, means 0 + 1 = 1. 01 <add> 1 = 10, means 1 + 1 = 2. 10 <add> 1 = 00, means 2 + 1 = 0, because it has % function embedded.So knock you head and realize the
operation:
Say youa bit r, the operation is defined as: b0 = b0 xor r & ~b1; b1 = b1 xor r & ~b0;you will find, this combination of bit operation does the
function.
So, when you have n SINGLE BIT numbers, they repeat by 3 except one which only appear once. Can you find the special one?
Lets do it:b0 = b1 = 0; For (r : nums) { b0b1 <add> r }; return b0;The fact is, bit operation can do in parallel in terms of bit position. i.e., the operation of position P & Q & any other positions can be done in parallel. Therefore the code becomes:
public int singleNumber(int[] A) {
int b0 = 0, b1 = 0;
for(int i = 0; i < A.length; i++){
b0 = (ones ^ A[i]) & ~b1;
b1 = (twos ^ A[i]) & ~b0;
}
return b0;
}
if you want to return the number that appears exactly twice, return b1.
Thank againest1 for his pioneering work.
看起来很有条理的解释, 实际上, 并没有讲出一个所以然, 也就是并没有解释出来完整的设计逻辑, 只是告诉了你为什么OP这里的这两行代码是对的;
I think many coder confused how to generate the code.
This is my analysis, use Truth table to generate code:
Consider every bit in a number, if this bit appear 3 times then set it to zero.
so here is 3 state of one bit, we can use two bit to indicate it.
we use 00 -> 01 -> 10 -> 00…
00: bit 1 appear 0 time.
01: bit 1 appear 1 time.
10: bit 1 appear 2 times.
so every bit 1 appear 3 times, the state will go to 00
but for the single number, every bit 1 in it, its status is 01
we can use two integer to represent the status, named first, second
Now problem is how to generate the code to change ‘first’ and ‘second’
I use truth table to generate the code, like this:
count every ‘1’ bit, 3 times to zero
so we need 3 status, 2 bit is enough
state: 00 -> 01 -> 10 -> 00…
so we can draw a truth table of first bit
A: first bit
B: second bit
C: input bitA B C NA NB 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 not define 1 1 1 not defineso
NA = ~ABC + A~B~C NB = ~A~BC + ~AB~C = ~A(B^C) NB is first, NA is second, so we should use last first when we calc next secondcode is :
int first = 0, second = 0; for (int i = 0; i < n; ++i) { int lastFirst = first; first = ~second & (first ^ A[i]); second = (~second&lastFirst&A[i])|(second&~lastFirst&~A[i]); } return first;
这个稍微靠谱一点, 而且他这个方法是适合general情形的;
This solution is awesome. And it can easily be extended to 4,5,6…
The core idea is as follows. For one element x occurring P+1 times, we use P intermediate values, M[P].
For these intermediate values, we want to construct a loop.
[0,0,…0] ----> [0,x,…0] ----> [0,0,x…0] … [0,0,…x] ----> [0,0,…0]. This can be achieved by following codes.for(int j=0;j<P;j++) { int tmp = -1; for(int k=0;k<P;k++) { if(k!=j) { tmp &= ~M[k]; } } M[j] = (x^M[j]) & tmp; }
首先澄清一个概念, 以前说&= ~mask是clear, 但是实际上这个并不完整: 只有当mask是1的时候, 才是clear; 这个在Pintos当时的情况下是既定的, 因为我们的代码就是这么设计的; 但是实际这里使用的时候, 就不一定是默认的设定;
他这里的做法, 其实就是用一个tmp, 走一遍, 我们只考虑图上显示的这个bit, 但是实际上所有的bit都在同时进行这个操作; 但是我们只考虑这一个bit位置;
当我们想要更新[j]这个位置的这个bit的时候, 我们要确定其他的地方(这个bit上)没有1了, 这个也就是他temp的作用: 在j以外的所有k上面, 尝试性clear, 如果有任何一个1, 那么就会被clear掉, temp这个bit就会变成0, 在最后& tmp的时候, 完成filter操作, 被清零回去, 也就是x的这个bit无法更新M[j]的这个bit;
比如涂上这个情况, 假如1这个位置对应的是M[t], 首先, x进来, 对这个bit的默认操作是xor, 所以是一个flip, 或者说加法的操作; 但是我们这里这个状态结束之后, 我们想让M[t]这个bit变成0(这个是默认的, 因为1直接xor到0); 然后我们想要让M[t-1]变成1, 所以我感觉他上面这个代码实际上不对;
后来发现, 他这里是对的, 我上面最后AC的代码就是根据这个改过来的:
public int singleNumber(int[] nums, int _K) {
int K = _K - 1;
int[] bits = new int[K];
for (int num : nums) {
for (int i = 0; i < K; i++) {
int mask = -1;
for (int j = 0; j < K; j++) if (j != i)
mask &= ~bits[j];
bits[i] = (bits[i] ^ num) & mask;
}
}
return bits[0];
}
一个图示:
砍了这个图, 应该还是能够很清楚的理解为什么用这样的做法; 对于一个bit, 你x进来了, 想要更新比如bits[i], 只有其他所有的bits[_ other than i]全都是0的时候, 才允许更新, 否则就不允许(& mask消除任何xor操作的结果);
这样一个算法也把我之前的那个证明的思路拓宽了, 这个设计的核心理念不是不允许全部等于1, 而是只允许一个等于1;
为了方便, 要包含0, 不然最后返回结果的时候很麻烦了; 所以最后的循环是: [0 0 0]->[0 0 1]->[0 1 0]->[1 0 0]->[0 0 0]这样的, 这个是出现4次(K等于4的情形), 注意这里bits数组长度是3, 不是4;
这个题目这里实现的这个算法, 可以理解为一个广义上面的设计一个rotating bit mask的操作; 好像比这个复杂一些; 单纯只是想要知道一个rotate的mask, 设计起来比这个简单多了;
实际上这里设计的是一个类似rotating counter的做法; K-1个bit构成一个counter(每一个bit位于一个不同的数字里面); 然后每次来一个num, 直接对应于这个bit的位置的进行一个对应的操作; 如果进来的是1, 应该让counter increment(具体表现是1的位置左移), 如果是0, 那么无所谓, 因为...不对, 如果进来的bit是0, 好像也是要分析mask的: 比如当前是0010000, 其实只有1这个位置的(这个i)的mask才是1, 其他的mask都是0, 而1这个位置, 最后xor0, 所以是保持原样, 然后mask是1, 所以不filter掉; 其他位置的是0xor0&0, 1这个位置是1xor0&1;
总体来说这个设计还是有点黑魔法的; 相比于自己手动一个一个的去数bit, 这个做法的优势是, 所有bit的运算都是同步进行的, parallel的;
另外, 补充一下关于这个做法的解释: 这个做法的还有一个特点就是, 每一个num进来之后, 你看我对i更新的顺序, 是右边往左边(低位往高位)移动的; 这个顺序也是导致了上面这个"查看所有其他的bit全都必须是0"的判断的原因:
首先你要搞清楚你的目标, 当前的bits数组里面, 只有一个是1, 其他的全都是0, 我希望只有当前这个1向左一位的这个数字完成0->1, 然后现在的1本身完成1->0, 其他的不许变化; 然后另外一点你要记得的是, 我死活是要把所有的bits都要xor上num的(尤其是对应的这个bit), 这个是不会改变的: 这个思路跟加法思路的差别在于, 加法思路, num(的这个bit)进来之后, 只影响最右边的最低位, 但是这个counter的思路, 我们要依赖的是, 把这个num的bit, 输入给所有的bits; 至于每一个bits自己怎么变化, 是他们自己的事情, 起码要保证信息提供足够了;
- 下面, 当你从右边开始往左边移动的时候, 我们的思路是这样的: 如果我们在往左的过程中, 还没有碰到过1, 那么我们应该屏蔽当前bit, 不许他变化; 这个操作的方式很简单, 直接判断所有其他位置有1就可以了;
- 当我们到了这个1的时候, 这个1的其他人全都是0, 所以这个1本身肯定不会被屏蔽, 他会完成xor num的操作(是0是1无所谓, 是1就是flip到0):
- 如果num进来的是1, 那么当前这个1就会变成0, 注意, 因为进来的是1, 所以我们希望当前这个bit的向左一位要完成一个0->1, 事实上, 现在就可以完成了, 因为我们现在的这个1刚刚被clear掉了(因为xor num), 那么马上下一个i移动到向左一个高位的时候, 这个高位的其他人全都是0, 他就不会被屏蔽, 就会成功完成0->1; 这样一个过程, 就很轻松的完成了我们希望唯一的这个1变成0, 这个1的上家变成0, 其他人全都屏蔽的操作;
- 假如num进来的是0, 那么我们当前的这个1不会变, 那么我们下一个i到了左边高一位的时候, 这个高一位还是被屏蔽: 因为原来的1并没有被清除; 这样也完成了原来的1没有变化的情况下, 别的0也不许变成1的操作;
we can think of this prolem is a ternary plus, if we do ternary plus for each bit of the number,
the 3 times number will reach 0, and only one number is not 0.
we can think of xor operation as no-carry binary plus, i.e., 0 ^ 1 = 0 + 1, 1^1 = 1+1 = 0 .
we can use (xor, and ,or) to implemnt quaternary plus, 0b10 + 0b01 = 0b11
and we can also use quaternary plus to implement ternary plus, by convert 0b11 to 0b00 after each plus.
class Solution {
public:
int singleNumber(int A[], int n) {
//a is the second bit, b is first bit, a = 0, b= 1 denote 0b01, c is the current number in array.
int a= 0, b = 0, c = 0;
for (int i = 0; i < n; i++)
{
c = A[i];
//begin quaternary plus.
a = a ^ (b & c);// only b = 1 c = 1 can let a+=1.
b = b ^ c;// b+=1.
//end quaternary plus and begin convert 0b11 to 0b00.
c = a & b;// use c as temp variable to record a & b, we change 0b11 to 0b00
a = a & ~c;// make a = 0 if a ==1 and b == 1.
b = b & ~c;//make b = 0 if a == 1 and b == 1
//end converting 0b11
}
// the a and b is the result of ternary plus of the number we fould.
return a | b;
}
};
理解到这个实际上是一个加法操作基本上就是对路子了; 具体的逻辑没有看了; 我觉得与其他这样慢慢搞, 不如多来一个carry数字, 这样...不对;
反正代码写的也是很清楚的, 实际上就是在普通的加法操作之后加一个post processing, 删除0b11这个state就行了; 之前的部分就是正常的0bxx这样的数字+1你怎么实现就是的了; 溢出的进位不用管;
@LoveTTn and whoever else, it’s extremely difficult and tedious to see how the code functions by simply looking at it. Take a step back and consider what we need - to determine how many occurrences of an integer there are up to a maximum of three. We need to build a 3 state counter.
How do we do that? Boolean logic. Consider a single bit input and how that would drive the internal state of a bit counter in the state table below. An input value ‘0’ does not change the internal state. Input of ‘1’ drives the counter from state 0, 1, 2 and resets back to zero.
The state table can be implemented as a boolean circuit with two XOR, two AND, and two NOT gates. That construction is reflected in the solution code. Other constructions with identical functionality are also possible.'A' 'twos' 'ones' 'twos' 'ones' 0 0 0 | 0 0 0 0 1 | 0 1 0 1 0 | 1 0 1 0 0 | 0 1 1 0 1 | 1 0 1 1 0 | 0 0for (int i = 0; i < A.size(); i++) { ones = (ones ^ a[i]) & ~twos; twos = (twos ^ a[i]) & ~ones; }We can extend the same approach to a 4-state counter, which works on the same problem if we want to find a single occurrence among multiple occurrences of 4 values. The state table extends by one count before resetting, and we have a new set of boolean logic. Again, other boolean constructions are possible for the same state table.
For 5 states we would need to add a third bit as a ‘threes’ variable and additional logic design.'A' 'twos' 'ones' 'twos' 'ones' 0 0 0 | 0 0 0 0 1 | 0 1 0 1 0 | 1 0 0 1 1 | 1 1 1 0 0 | 0 1 1 0 1 | 1 0 1 1 0 | 1 1 1 1 1 | 0 0for (int i = 0; i < A.size(); i++) { ones = (ones ^ A[i]); twos = (twos | A[i]) & (~A[i] | (ones ^ twos)); }Now here’s the problem. The boolean code, which is the logic representation of the state table, is practically unreadable and gets substantially worse as the table grows. Going backwards from the boolean code to the state table is extremely painful and tedious - like disassembling machine code.
This solution is basically the result of a human compiler. Definitely novel, but practical? I’m thinking not so much. So don’t worry if you can’t understand the code immediately by simply looking at it. Nobody can.
也是一个真值表的做法, 但是我认为OP本来的做法并不是用真值表来做的, 而是用我上面的拓展思路来做的;
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 k counts, we require 2^m >= k, which implies m >= 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!
他这个算法的核心就在这里, 就是自己实现这个加法的逻辑; 后面就是在加法的基础上, 加了一个cutoff的post processing; 这里的逻辑其实也是不复杂的, 对于一个bit xm, 只有右边全是11..11, 然后进来的i也是1的时候, 那么我们知道xm肯定要flip(注意, 不是set, 因为如果原来是1, 那么应该flip成1). 注意这里的顺序, 从高到低, 所以最高的一位不可能有一个1->0(代表溢出)的flip, 因为我们的m选择的时候就是保证能够涵盖K的(2^m>=k);
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的选择也不复杂;
看到这里, 应该是能意识到这个算法是可以很generalize的实现的, 后面好像也是确实有人给出了这样一个非常general的实现;
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.
想法是对的, 证明方向也是对的, 但是证明啰嗦了: 所有出现了k次的数字肯定都是无所谓的, 最后就是single number自己, 你就相当于从头到尾就只有这p'个single number, 那么自然是只有这个number等于1的bit, 才能让最后任何一个xj的bit r出现1; 这个其实本身的道理是很直观的;
上面讲的不是很严谨, 不过大概思路是对的; 你就考虑比如我们p'等于3的情况, 你比如有2个5, 其他的出现k次的都不用管了; 你现在就让5出现3次, 这个对于所有的x有什么影响? 你脑子里, 5始终就是一个101的表达, 有1的两个bit, 出现了2次, 那么我们就会有:
x1 1 0 1
x0 0 0 0
5 1 0 1
不知道这样看是不是很直观, 只要是你5有1的bit上面, 那么最终肯定有一个x对应的这个bit上面也是1, 事实上这个x完全就复制了5的binary表达; 这个原因是因为这里设计的是一个加法模式, 你就盯住一个bit, 5的这一个bit, 在当前bit的x数组表达当中, 这个counter最后表达的就是2(竖着看的10), 那么肯定有一个x, 也就是这里的x1, 是对应的...不知道怎么表达, 反正这个意思应该已经很明显了; 主要原因是因为这里x数组针对某一个bit, 设置的是一个counter, 因为p' < k, 所以最后在bit0上面的这个counter, 5的bit1是有2次, 那么x1[0]x0[0]组成的这个counter, 肯定必须要显示10, 也就是肯定至少有一个x?[0]是1; 更进一步, 因为我们现在实际上count的只有5这一个数字, 所以所有bit上面的counter其实都是同步count的, 所以最后只要是有1的这个x, 他的所有的bit全都是跟5一样的;
不知道讲清楚没有;
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 = 1
k is 2, then m = 1, we need only one 32-bit integer (x1) as the counter. And 2^m = k so 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 = 1
k is 3, then m = 2, we need two 32-bit integers(x2, x1) as the counter. And 2^m > k so we do need a mask. Write k in its binary form: k = '11', then k1 = 1, k2 = 1, so we have mask = ~(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 = 3
k is 5, then m = 3, we need three 32-bit integers(x3, x2, x1) as the counter. And 2^m > k so we need a mask. Write k in its binary form: k = '101', then k1 = 1, k2 = 0, k3 = 1, so we have mask = ~(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). }Lastly I would like to thank those for providing feedbacks to make this post better. Hope it helps and happy coding!
上面OP自己的代码实际上还是有点手动的成分在里面的, 下面这个代码声称是general的, 没有仔细看了; 不过这个OP的这个算法本身确实是可以拓展到k和p都是任意数的情况的;
public class Solution {
public int singleNumber(int[] nums) {
return generalSolution(nums, 3, 1);
}
public int generalSolution(int[] nums, int all_rep, int single_rep) {
int m = bit_length(all_rep);
int[] counters = new int[m];
for (int n : nums) {
//counting
for (int i = m-1; i >=0; i--) {
int carr = n;
for (int j = i-1; j >= 0; j--) {
carr &= counters[j];
}
counters[i] ^= carr;
}
//mask
int mask = ~0;
for (int i = m-1; i >= 0; i--) {
if (((all_rep >> i) & 1) == 1) {
mask &= counters[i];
} else {
mask &= ~counters[i];
}
}
mask = ~mask;
for (int i = m-1; i>=0; i--) {
counters[i] &= mask;
}
}
//find the return value
single_rep %= all_rep;
for (int i = 0; single_rep != 0; i++) {
if ((single_rep & 1) == 1) {
return counters[i];
} else {
single_rep >>= 1;
}
}
return -1; //error
}
public int bit_length( int bits ) {
int res = 0;
while (bits > 0) {
bits >>= 1;
res++;
}
return res;
}
}
https://leetcode.com/problems/single-number-ii/discuss/43368/Constant-space-solution/42407
To solve this problem using only constant space, you have to rethink how the numbers are being represented in computers – using bits.
If you sum the ith bit of all numbers and mod 3, it must be either 0 or 1 due to the constraint of this problem where each number must appear either three times or once. This will be the ith bit of that “single number”.
A straightforward implementation is to use an array of size 32 to keep track of the total count of ith bit.
int singleNumber(int A[], int n) {
int count[32] = {0};
int result = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < n; j++) {
if ((A[j] >> i) & 1) {
count[i]++;
}
}
result |= ((count[i] % 3) << i);
}
return result;
}
We can improve this based on the previous solution using three bitmask variables:
- ones as a bitmask to represent the ith bit had appeared once.
- twos as a bitmask to represent the ith bit had appeared twice.
- threes as a bitmask to represent the ith bit had appeared three times.
When the ith bit had appeared for the third time, clear the ith bit of both ones and twos to 0. The final answer will be the value of ones.
int singleNumber(int A[], int n) {
int ones = 0, twos = 0, threes = 0;
for (int i = 0; i < n; i++) {
twos |= ones & A[i];
ones ^= A[i];
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
这个好像是2013年, 第一个给出答案的人了; 他的思路跟上面那个general做法其实是类似的, 他这里的这个threes实际上就是上面的mask, 不过不是最general的情形: 他这里是利用了3是0b11的fact;
好像这个帖子里面大量这种先加法, 然后cutoff的做法;
this kind of question the key idea is design a counter that record state. the problem can be every one occurs K times except one occurs M times. for this question, K =3 ,M = 1(or 2) .
so to represent 3 state, we need two bit. let say it is a and b, and c is the incoming bit.
then we can design a table to implement the state move.current incoming next a b c a b 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 0 0like circuit design, we can find out what the next state will be with the incoming bit.( we only need find the ones)
then we have for a to be 1, we havecurrent incoming next a b c a b 1 0 0 1 0 0 1 1 1 0and this is can be represented by
a=a&~b&~c + ~a&b&cand b can do the same we , and we find that
b= ~a&b&~c+~a&~b&cand this is the final formula of a and b and just one of the result set, because for different state move table definition, we can generate different formulas, and this one is may not the most optimised. as you may see other’s answer that have a much simple formula, and that formula also corresponding to specific state move table. (if you like ,you can reverse their formula to a state move table, just using the same way but reversely)
for this questions we need to find the except one
as the question don’t say if the one appears one time or two time ,
so for ab both01 10 => 1 00 => 0we should return a|b;
this is the key idea , we can design any based counter and find the occurs any times except one .
here is my code. with comment.public class Solution { public int singleNumber(int[] nums) { //we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero. //#curent income ouput //# ab c/c ab/ab //# 00 1/0 01/00 //# 01 1/0 10/01 //# 10 1/0 00/10 // a=~abc+a~b~c; // b=~a~bc+~ab~c; int a=0; int b=0; for(int c:nums){ int ta=(~a&b&c)|(a&~b&~c); b=(~a&~b&c)|(~a&b&~c); a=ta; } //we need find the number that is 01,10 => 1, 00 => 0. return a|b; } }this is a general solution . and it comes from the Circuit Design on course digital logic.
基本上还是一个真值表的做法; 比较的general, 不过感觉如果真的是自己动手实现还是挺容易犯错误的;
看到这里下来, 设计循环这个肯定是核心思想, 但是具体实现方式, 也就是怎么想到对应的代码, 有三个套路:
- 逻辑真值表穷举: 需要多加一个input作为额外的输入
- 加法+cutoff;
- rotating counter;
三种做法各有千秋; 第三种做法看起来是最neat的, 但是老实说其实我现在都还没有完全的掌握;
public int singleNumber(int[] nums) {
int res = 0;
for(int i = 0; i < 32; i++){
int sum = 0;
for(int n: nums)
if((n >> i & 1) == 1)
sum++;
sum %= 3;
res |= sum<<i;
}
return res;
}
基本的count做法, 没有仔细看了; 对了, 这种做法是不需要构建循环的;
这题其实直接用一个32层循环来count, 好简单;
不过这种做法好像没有办法generalize到p不等于1的情况;
不对, 可以的; 比如k=3, p=2, 最后剩下的sum mod完之后就是2, 然后你判断一下>0就是1, 然后or到res里面去就行了; p本身具体多少对最后这个single number是谁是没有影响的;
Great solution! But I think this solution will not be correct if there is a number appeared two times, like[1,1,1,2,2,2,3,3]. It will return 6, instead of 3. This solution works for the number whose occurrences % 3 is 1. To make it work for this case,
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 == 1) {
ans |= sum << i;
}
if(sum == 2) {
ans |= sum/2 << i
}
}
return ans;
}
这个就很瓜了, 直接判断>0就行了;
submission好像抓到第一个解法原来的作者的代码了:
class Solution {
public int singleNumber(int[] nums) {
// 1. 存入ones
// 2. 清空ones， 存入twos
// 3. 清空twos
int ones = 0, twos = 0;
for(int i = 0; i < nums.length; i++){
ones = (ones ^ nums[i]) & ~twos;
twos = (twos ^ nums[i]) & ~ones;
}
return ones;
}
}
好像也可以这么理解;
注意他是有一个明确的清空的概念在里面的;
不对, 不是很理解他这里这个中文逻辑;
Problem Description
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?
Difficulty:Medium
Total Accepted:131.5K
Total Submissions:309.2K
Contributor:LeetCode
Related Topics
bit manipulation
Similar Questions
Single NumberSingle Number III