哪里去买SPNG?# Stock
c*p
1 楼
不用extra space，要怎么做？
顺便问一下single number i
我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
法？
谢谢！
顺便问一下single number i
我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
法？
谢谢！
y*1
2 楼
Scottrade好像不能
c*u
3 楼
创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
空间复杂度O(1).
int sol1(int A[], int n)
{
int count[32];
int result = 0;
for (int i = 0;i < 32;++i) {
count[i] = 0;
for (int j = 0;j < n;++j) {
if ((A[j] >> i) & 1) count[i] = (count[i] + 1) % 3;
}
result |= (count[i] << i);
}
return result;
}
另一个方法，同样的原理，用3个整数来表示INT的各位的出现次数情况，one表示出现
了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。
int sol2(int A[], int n)
{
int one = 0, two = 0, three = 0;
for (int i = 0;i < n;++i) {
two |= one & A[i];
one ^= A[i];
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
空间复杂度O(1).
int sol1(int A[], int n)
{
int count[32];
int result = 0;
for (int i = 0;i < 32;++i) {
count[i] = 0;
for (int j = 0;j < n;++j) {
if ((A[j] >> i) & 1) count[i] = (count[i] + 1) % 3;
}
result |= (count[i] << i);
}
return result;
}
另一个方法，同样的原理，用3个整数来表示INT的各位的出现次数情况，one表示出现
了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。
int sol2(int A[], int n)
{
int one = 0, two = 0, three = 0;
for (int i = 0;i < n;++i) {
two |= one & A[i];
one ^= A[i];
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
c*p
4 楼
有点类似于bit vector是么？
最开始我有想到bit vector，可是发现有negative的数。。。
这个方法好，我捧回去读读～
谢谢咯！
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
最开始我有想到bit vector，可是发现有negative的数。。。
这个方法好，我捧回去读读～
谢谢咯！
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
f*t
5 楼
这个比网上那个解释的清楚，赞！
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
y*n
6 楼
Very elegant.
c*p
7 楼
忽然想起来，这个是cc150里的题？？
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
c*p
8 楼
长度为32的数组，为什么空间复杂度是1？？
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
p*2
9 楼
刚做了一下1
(defn singleNumber [A] (reduce bit-xor A))
(defn singleNumber [A] (reduce bit-xor A))
c*u
10 楼
使用常量空间，自然是O(1)。
难道会是O(32)吗。。。
【在 c********p 的大作中提到】
: 长度为32的数组，为什么空间复杂度是1？？
难道会是O(32)吗。。。
【在 c********p 的大作中提到】
: 长度为32的数组，为什么空间复杂度是1？？
g*j
11 楼
我做了一个，类似三色旗的题目，把小于，等于，大于的数排列，然后看index
这样行么？
【在 c********p 的大作中提到】
: 不用extra space，要怎么做？
: 顺便问一下single number i
: 我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
: 法？
: 谢谢！
这样行么？
【在 c********p 的大作中提到】
: 不用extra space，要怎么做？
: 顺便问一下single number i
: 我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
: 法？
: 谢谢！
G*C
12 楼
第一个解法要32o(n)吧，这个太大常数项，还不如排序
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
c*p
13 楼
你的第2个方法，好深奥哦。。
没看懂。。。
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
没看懂。。。
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
r*7
14 楼
之前做这题时候在网上看到的，拿来献丑下：
public int singleNumber(int[] A) {
int a = 0; int b = 0; int c = 0;
for(int i=0;i
a ^= A[i]; //从A里面删除 出现两次的
c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
a &= c; //然后删除A里三次的
b &= c; //删除B里三次的
}
return a;
}
public int singleNumber(int[] A) {
int a = 0; int b = 0; int c = 0;
for(int i=0;i
a ^= A[i]; //从A里面删除 出现两次的
c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
a &= c; //然后删除A里三次的
b &= c; //删除B里三次的
}
return a;
}
c*p
15 楼
太复杂了，我的智商跟不上了。。。
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
c*p
16 楼
不用extra space，要怎么做？
顺便问一下single number i
我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
法？
谢谢！
顺便问一下single number i
我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
法？
谢谢！
c*u
17 楼
创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
空间复杂度O(1).
int sol1(int A[], int n)
{
int count[32];
int result = 0;
for (int i = 0;i < 32;++i) {
count[i] = 0;
for (int j = 0;j < n;++j) {
if ((A[j] >> i) & 1) count[i] = (count[i] + 1) % 3;
}
result |= (count[i] << i);
}
return result;
}
另一个方法，同样的原理，用3个整数来表示INT的各位的出现次数情况，one表示出现
了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。
int sol2(int A[], int n)
{
int one = 0, two = 0, three = 0;
for (int i = 0;i < n;++i) {
two |= one & A[i];
one ^= A[i];
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
空间复杂度O(1).
int sol1(int A[], int n)
{
int count[32];
int result = 0;
for (int i = 0;i < 32;++i) {
count[i] = 0;
for (int j = 0;j < n;++j) {
if ((A[j] >> i) & 1) count[i] = (count[i] + 1) % 3;
}
result |= (count[i] << i);
}
return result;
}
另一个方法，同样的原理，用3个整数来表示INT的各位的出现次数情况，one表示出现
了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。
int sol2(int A[], int n)
{
int one = 0, two = 0, three = 0;
for (int i = 0;i < n;++i) {
two |= one & A[i];
one ^= A[i];
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
c*p
18 楼
有点类似于bit vector是么？
最开始我有想到bit vector，可是发现有negative的数。。。
这个方法好，我捧回去读读～
谢谢咯！
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
最开始我有想到bit vector，可是发现有negative的数。。。
这个方法好，我捧回去读读～
谢谢咯！
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
f*t
19 楼
这个比网上那个解释的清楚，赞！
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
y*n
20 楼
Very elegant.
c*p
21 楼
忽然想起来，这个是cc150里的题？？
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
c*p
22 楼
长度为32的数组，为什么空间复杂度是1？？
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
p*2
23 楼
刚做了一下1
(defn singleNumber [A] (reduce bit-xor A))
(defn singleNumber [A] (reduce bit-xor A))
c*u
24 楼
使用常量空间，自然是O(1)。
难道会是O(32)吗。。。
【在 c********p 的大作中提到】
: 长度为32的数组，为什么空间复杂度是1？？
难道会是O(32)吗。。。
【在 c********p 的大作中提到】
: 长度为32的数组，为什么空间复杂度是1？？
g*j
25 楼
我做了一个，类似三色旗的题目，把小于，等于，大于的数排列，然后看index
这样行么？
【在 c********p 的大作中提到】
: 不用extra space，要怎么做？
: 顺便问一下single number i
: 我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
: 法？
: 谢谢！
这样行么？
【在 c********p 的大作中提到】
: 不用extra space，要怎么做？
: 顺便问一下single number i
: 我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
: 法？
: 谢谢！
G*C
26 楼
第一个解法要32o(n)吧，这个太大常数项，还不如排序
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
c*p
27 楼
你的第2个方法，好深奥哦。。
没看懂。。。
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
没看懂。。。
【在 c****u 的大作中提到】
: 创建一个长度为32的数组a，a[i]表示所有数字在i位出现的次数。
: 假如a[i]是3的整数倍，则忽略；否则就把该位取出来组成答案。
: 空间复杂度O(1).
: int sol1(int A[], int n)
: {
: int count[32];
: int result = 0;
: for (int i = 0;i < 32;++i) {
: count[i] = 0;
: for (int j = 0;j < n;++j) {
r*7
28 楼
之前做这题时候在网上看到的，拿来献丑下：
public int singleNumber(int[] A) {
int a = 0; int b = 0; int c = 0;
for(int i=0;i
a ^= A[i]; //从A里面删除 出现两次的
c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
a &= c; //然后删除A里三次的
b &= c; //删除B里三次的
}
return a;
}
public int singleNumber(int[] A) {
int a = 0; int b = 0; int c = 0;
for(int i=0;i
a ^= A[i]; //从A里面删除 出现两次的
c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
a &= c; //然后删除A里三次的
b &= c; //删除B里三次的
}
return a;
}
c*p
29 楼
太复杂了，我的智商跟不上了。。。
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
M*s
30 楼
我觉得原本的code不必要的复杂了
重写了一遍，不算comments少了两行，也觉得容易理解些
整体思路是：整数的32个bits，出现次数mod 3后必余0, 1, 2
其中余1的就是答案
int singleNumber(int A[], int n) {
int n1=0, n2=0; // n1为mod 3余1的bits，n2为mod 3余2的bits
for (int i=0; i
// 若「原本就余2且bit为0」或「原本余1且bit为1」，则该bit更新后余2
n2 = (n2&~A[i]) | (n1&A[i]);
// 若「原本就余1且bit为0」或「原本余0且bit为1」，则该bit更新后余1
n1 = (n1&~A[i]) | (n0&A[i]);
}
return n1; // 余1的bits即为答案
}
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
重写了一遍，不算comments少了两行，也觉得容易理解些
整体思路是：整数的32个bits，出现次数mod 3后必余0, 1, 2
其中余1的就是答案
int singleNumber(int A[], int n) {
int n1=0, n2=0; // n1为mod 3余1的bits，n2为mod 3余2的bits
for (int i=0; i
// 若「原本就余2且bit为0」或「原本余1且bit为1」，则该bit更新后余2
n2 = (n2&~A[i]) | (n1&A[i]);
// 若「原本就余1且bit为0」或「原本余0且bit为1」，则该bit更新后余1
n1 = (n1&~A[i]) | (n0&A[i]);
}
return n1; // 余1的bits即为答案
}
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
M*s
31 楼
我觉得原本的code不必要的复杂了
重写了一遍，不算comments少了两行，也觉得容易理解些
整体思路是：整数的32个bits，出现次数mod 3后必余0, 1, 2
其中余1的就是答案
int singleNumber(int A[], int n) {
int n1=0, n2=0; // n1为mod 3余1的bits，n2为mod 3余2的bits
for (int i=0; i
// 若「原本就余2且bit为0」或「原本余1且bit为1」，则该bit更新后余2
n2 = (n2&~A[i]) | (n1&A[i]);
// 若「原本就余1且bit为0」或「原本余0且bit为1」，则该bit更新后余1
n1 = (n1&~A[i]) | (n0&A[i]);
}
return n1; // 余1的bits即为答案
}
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
重写了一遍，不算comments少了两行，也觉得容易理解些
整体思路是：整数的32个bits，出现次数mod 3后必余0, 1, 2
其中余1的就是答案
int singleNumber(int A[], int n) {
int n1=0, n2=0; // n1为mod 3余1的bits，n2为mod 3余2的bits
for (int i=0; i
// 若「原本就余2且bit为0」或「原本余1且bit为1」，则该bit更新后余2
n2 = (n2&~A[i]) | (n1&A[i]);
// 若「原本就余1且bit为0」或「原本余0且bit为1」，则该bit更新后余1
n1 = (n1&~A[i]) | (n0&A[i]);
}
return n1; // 余1的bits即为答案
}
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
H*7
32 楼
2爷去年玩cloj呢。
【在 p*****2 的大作中提到】
: 刚做了一下1
: (defn singleNumber [A] (reduce bit-xor A))
【在 p*****2 的大作中提到】
: 刚做了一下1
: (defn singleNumber [A] (reduce bit-xor A))
相关阅读