c********p
发帖数: 1969 | 1 不用extra space，要怎么做？
顺便问一下single number i
我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
法？
谢谢！ |
c****u
发帖数: 59 | 2 创建一个长度为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;
} |
c********p
发帖数: 1969 | 3 有点类似于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) {
|
f*****t
发帖数: 13 | 4 这个比网上那个解释的清楚，赞！
【在 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
发帖数: 1594 | |
c********p
发帖数: 1969 | 6 忽然想起来，这个是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********p
发帖数: 1969 | 7 长度为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) {
|
p*****2
发帖数: 21240 | 8 刚做了一下1
(defn singleNumber [A] (reduce bit-xor A)) |
c****u
发帖数: 59 | 9 使用常量空间，自然是O(1)。
难道会是O(32)吗。。。
【在 c********p 的大作中提到】
: 长度为32的数组，为什么空间复杂度是1？？
|
g***j
发帖数: 1275 | 10 我做了一个，类似三色旗的题目，把小于，等于，大于的数排列，然后看index
这样行么？
【在 c********p 的大作中提到】
: 不用extra space，要怎么做？
: 顺便问一下single number i
: 我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
: 法？
: 谢谢！
|
|
|
G**C
发帖数: 365 | 11 第一个解法要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********p
发帖数: 1969 | 12 你的第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) {
|
r********7
发帖数: 102 | 13 之前做这题时候在网上看到的，拿来献丑下：
public int singleNumber(int[] A) {
int a = 0; int b = 0; int c = 0;
for(int i=0;i
b |= a&A[i]; //出现两次的 就加到B里面
a ^= A[i]; //从A里面删除 出现两次的
c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
a &= c; //然后删除A里三次的
b &= c; //删除B里三次的
}
return a;
} |
c********p
发帖数: 1969 | 14 太复杂了，我的智商跟不上了。。。
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i: b |= a&A[i]; //出现两次的 就加到B里面
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
|
c********p
发帖数: 1969 | 15 不用extra space，要怎么做？
顺便问一下single number i
我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
法？
谢谢！ |
c****u
发帖数: 59 | 16 创建一个长度为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;
} |
c********p
发帖数: 1969 | 17 有点类似于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) {
|
f*****t
发帖数: 13 | 18 这个比网上那个解释的清楚，赞！
【在 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
发帖数: 1594 | |
c********p
发帖数: 1969 | 20 忽然想起来，这个是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********p
发帖数: 1969 | 21 长度为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) {
|
p*****2
发帖数: 21240 | 22 刚做了一下1
(defn singleNumber [A] (reduce bit-xor A)) |
c****u
发帖数: 59 | 23 使用常量空间，自然是O(1)。
难道会是O(32)吗。。。
【在 c********p 的大作中提到】
: 长度为32的数组，为什么空间复杂度是1？？
|
g***j
发帖数: 1275 | 24 我做了一个，类似三色旗的题目，把小于，等于，大于的数排列，然后看index
这样行么？
【在 c********p 的大作中提到】
: 不用extra space，要怎么做？
: 顺便问一下single number i
: 我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方
: 法？
: 谢谢！
|
G**C
发帖数: 365 | 25 第一个解法要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********p
发帖数: 1969 | 26 你的第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) {
|
r********7
发帖数: 102 | 27 之前做这题时候在网上看到的，拿来献丑下：
public int singleNumber(int[] A) {
int a = 0; int b = 0; int c = 0;
for(int i=0;i
b |= a&A[i]; //出现两次的 就加到B里面
a ^= A[i]; //从A里面删除 出现两次的
c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
a &= c; //然后删除A里三次的
b &= c; //删除B里三次的
}
return a;
} |
c********p
发帖数: 1969 | 28 太复杂了，我的智商跟不上了。。。
【在 r********7 的大作中提到】
: 之前做这题时候在网上看到的，拿来献丑下：
: public int singleNumber(int[] A) {
: int a = 0; int b = 0; int c = 0;
: for(int i=0;i: b |= a&A[i]; //出现两次的 就加到B里面
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
|
M**********s
发帖数: 8 | 29 我觉得原本的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
int n0 = ~(n1|n2); // 若非余1也非余2，就是余0了
// 若「原本就余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: b |= a&A[i]; //出现两次的 就加到B里面
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
|
M**********s
发帖数: 8 | 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
int n0 = ~(n1|n2); // 若非余1也非余2，就是余0了
// 若「原本就余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: b |= a&A[i]; //出现两次的 就加到B里面
: a ^= A[i]; //从A里面删除 出现两次的
: c = ~(a&b); //如果是三次的 就会同时出现在A和B里面，
: a &= c; //然后删除A里三次的
: b &= c; //删除B里三次的
: }
|
|
|
H******7
发帖数: 1728 | 31 2爷去年玩cloj呢。
【在 p*****2 的大作中提到】
: 刚做了一下1
: (defn singleNumber [A] (reduce bit-xor A))
|
