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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 长度为32的数组,为什么空间复杂度是1??
|
g***j 发帖数: 1275 | 10 我做了一个,类似三色旗的题目,把小于,等于,大于的数排列,然后看index
这样行么?
【在 c********p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不用extra space,要怎么做? : 顺便问一下single number i : 我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方 : 法? : 谢谢!
|
|
|
G**C 发帖数: 365 | 11 第一个解法要32o(n)吧,这个太大常数项,还不如排序
【在 c****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 之前做这题时候在网上看到的,拿来献丑下: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 长度为32的数组,为什么空间复杂度是1??
|
g***j 发帖数: 1275 | 24 我做了一个,类似三色旗的题目,把小于,等于,大于的数排列,然后看index
这样行么?
【在 c********p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不用extra space,要怎么做? : 顺便问一下single number i : 我用hashtable 来记录出现次数。然后iterate hashtable的keyset。有没有更好的方 : 法? : 谢谢!
|
G**C 发帖数: 365 | 25 第一个解法要32o(n)吧,这个太大常数项,还不如排序
【在 c****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 创建一个长度为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 之前做这题时候在网上看到的,拿来献丑下: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 之前做这题时候在网上看到的,拿来献丑下: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 之前做这题时候在网上看到的,拿来献丑下: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 刚做了一下1 : (defn singleNumber [A] (reduce bit-xor A))
|