s******e
发帖数: 108 | 1 数组中有1个数出现一次，其他数出现三次，怎么求出这个出现1次的数
求不用额外内存的O(n)的方法，谢谢
可以constant的内存 |
l*****a
发帖数: 14598 | 2 好歹用点内存把
【在 s******e 的大作中提到】
: 数组中有1个数出现一次，其他数出现三次，怎么求出这个出现1次的数
: 求不用额外内存的O(n)的方法，谢谢
: 可以constant的内存
|
d**e
发帖数: 6098 | 3 不用的话，是不是只能O(n^2)了?
【在 l*****a 的大作中提到】
: 好歹用点内存把
|
e*****e
发帖数: 1275 | 4 题目是不时错了？是两次而不是三次？
两次就XOR |
l*****a
发帖数: 14598 | 5 3次用bitmap
【在 e*****e 的大作中提到】
: 题目是不时错了？是两次而不是三次？
: 两次就XOR
|
l***i
发帖数: 1309 | 6 How would you do this if you are allowed O(n) extra memory? |
d**e
发帖数: 6098 | 7 hash is a simple one
【在 l***i 的大作中提到】
: How would you do this if you are allowed O(n) extra memory?
|
s******e
发帖数: 108 | 8 可以bitwise mode 3
【在 d**e 的大作中提到】
: 不用的话，是不是只能O(n^2)了?
|
s******e
发帖数: 108 | 9 one idea is to counting or summing number of the bit(0|1)
and then mod the counting number by 3
malleye (smalleye) 的大作中提到: 】 |
s*****y
发帖数: 897 | 10 You mean convert all the integer to binary.
Then add all the bit in each postion then mod 3?
for example:
1 0001
3 0011
3 0011
3 0011
2 0010
2 0010
2 0010
+ |
|
|
s******e
发帖数: 108 | 11 exactly
【在 s*****y 的大作中提到】
: You mean convert all the integer to binary.
: Then add all the bit in each postion then mod 3?
: for example:
: 1 0001
: 3 0011
: 3 0011
: 3 0011
: 2 0010
: 2 0010
: 2 0010
|
s*****y
发帖数: 897 | 12 Did they interviewer require to write the code or just tell the idea at that
time?
【在 s******e 的大作中提到】
: exactly
|
s******e
发帖数: 108 | 13 do not know, get the question from careercup
刚刚想明白
that
【在 s*****y 的大作中提到】
: Did they interviewer require to write the code or just tell the idea at that
: time?
|
s*****y
发帖数: 897 | 14 今天刚在careerup看到的一个很牛的答案，但是看不懂思路，但是结果肯定是对的。
int main()
{
int B[] = {1,1,1,3,3,3,20,4,4,4};
int ones = 0 ;
int twos = 0 ;
int not_threes;
int x ;
for( i=0; i< 10; i++ )
{
x = B[i];
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}
printf("\n unique element = %d \n", ones );
return 0;
} |
a****s
发帖数: 9 | 15 用quicksort 的idea, 找一个pivot, 然后partition, 扔掉有3n个elements 的
partition, 如果两个partition都有3n个elements, 那么pivot就是要找的element. |
M*****e
发帖数: 568 | 16 这个变量名已经说得很明确了，
ones就是所有出现过一次的，所以每次更新用xor （注意后面去除了三次的）。
twos就是出现过两次的，更新的意思就是如果当前数b[i]在ones中存在, b[i]&ones，
就加到twos里面。
three就是一次和两次都出现过的，所以要从ones和twos中每次去除, & not_threes
【在 s*****y 的大作中提到】
: 今天刚在careerup看到的一个很牛的答案，但是看不懂思路，但是结果肯定是对的。
: int main()
: {
: int B[] = {1,1,1,3,3,3,20,4,4,4};
: int ones = 0 ;
: int twos = 0 ;
: int not_threes;
: int x ;
: for( i=0; i< 10; i++ )
: {
|
M*****e
发帖数: 568 | 17
复杂度上也是线性的，不过就没有上面位运算的牛逼了。
【在 a****s 的大作中提到】
: 用quicksort 的idea, 找一个pivot, 然后partition, 扔掉有3n个elements 的
: partition, 如果两个partition都有3n个elements, 那么pivot就是要找的element.
|
s*****y
发帖数: 897 | 18 looks like the ones twos and no-threes mean the bit position?
Is it?
【在 M*****e 的大作中提到】
: 这个变量名已经说得很明确了，
: ones就是所有出现过一次的，所以每次更新用xor （注意后面去除了三次的）。
: twos就是出现过两次的，更新的意思就是如果当前数b[i]在ones中存在, b[i]&ones，
: 就加到twos里面。
: three就是一次和两次都出现过的，所以要从ones和twos中每次去除, & not_threes
|
r*****l
发帖数: 2859 | 19 这这，如果第一个数是4呢？
【在 s*****y 的大作中提到】
: You mean convert all the integer to binary.
: Then add all the bit in each postion then mod 3?
: for example:
: 1 0001
: 3 0011
: 3 0011
: 3 0011
: 2 0010
: 2 0010
: 2 0010
|
s*****y
发帖数: 897 | 20 what do you mean? There is only one number that happen once?
【在 r*****l 的大作中提到】
: 这这，如果第一个数是4呢？
|
|
|
r*****l
发帖数: 2859 | 21 你那个0067哪来的？
You mean convert all the integer to binary.
Then add all the bit in each postion then mod 3?
for example:
1 0001
3 0011
3 0011
3 0011
2 0010
2 0010
2 0010
+
【在 s*****y 的大作中提到】
: what do you mean? There is only one number that happen once?
|
r*****l
发帖数: 2859 | 22 所有数转换成三进制。
1，每个数个位相加，取结果最低位，作为个位。
2，每个数十位相加，取结果最低位，作为十位。
。。。
然后再转成10进制。
20,3,3,3,7,7,7
20 - 202 (三进制)
3 - 10
3 - 10
3 - 10
7 - 21
7 - 21
7 - 21
个位 2+1+1+1=12 => 2
十位 1+1+1+2+2+2=0 => 0
百位 2 => 2
结果 202（三进制）=> 20
【在 s******e 的大作中提到】
: 数组中有1个数出现一次，其他数出现三次，怎么求出这个出现1次的数
: 求不用额外内存的O(n)的方法，谢谢
: 可以constant的内存
|
s*****y
发帖数: 897 | 23 SORRY. My typo. should be 0064
【在 r*****l 的大作中提到】
: 你那个0067哪来的？
:
: You mean convert all the integer to binary.
: Then add all the bit in each postion then mod 3?
: for example:
: 1 0001
: 3 0011
: 3 0011
: 3 0011
: 2 0010
|
s*****y
发帖数: 897 | 24 But then 1 happen only twice. The question said that only one number happen
once and all the other number happen 3 times.
【在 r*****l 的大作中提到】
: 所有数转换成三进制。
: 1，每个数个位相加，取结果最低位，作为个位。
: 2，每个数十位相加，取结果最低位，作为十位。
: 。。。
: 然后再转成10进制。
: 20,3,3,3,7,7,7
: 20 - 202 (三进制)
: 3 - 10
: 3 - 10
: 3 - 10
|
r*****l
发帖数: 2859 | 25 如果是4,3,3,3,2,2,2，用你的方法
100
011
011
011
010
010
010
+ |
d**e
发帖数: 6098 | 26 the mod is
1%3
6%3
3%3
not 163%3
【在 r*****l 的大作中提到】
: 如果是4,3,3,3,2,2,2，用你的方法
: 100
: 011
: 011
: 011
: 010
: 010
: 010
: +
|
s*****y
发帖数: 897 | 27 sorry. The mod operaton is for each bit position, not for the sum.
So it is really tricky to code the problem in this way.
163 is 1mode3 6mod3 3mod3 so result is 100.
【在 r*****l 的大作中提到】
: 如果是4,3,3,3,2,2,2，用你的方法
: 100
: 011
: 011
: 011
: 010
: 010
: 010
: +
|
r*****l
发帖数: 2859 | 28 This makes sense. Thanks
【在 s*****y 的大作中提到】
: sorry. The mod operaton is for each bit position, not for the sum.
: So it is really tricky to code the problem in this way.
: 163 is 1mode3 6mod3 3mod3 so result is 100.
|
m**q
发帖数: 189 | 29 Good point, a few details though:
1 1 2 2 3 2 4 1 4 4
For example, we picked 2 as pivot, as we divided the array to
the following
1 1 1 2 2 2 3 4 4 4
< 2 pivot >= 2
Then both sides have 3n elements, but pivot value 2 is not the
one we want to find. In this case we can save discard the left
half, and simply compare pivot with its next neighbour on the right,
if they are not equal then we're done and pivot is the one, otherwise
continue with the right half.
【在 a****s 的大作中提到】
: 用quicksort 的idea, 找一个pivot, 然后partition, 扔掉有3n个elements 的
: partition, 如果两个partition都有3n个elements, 那么pivot就是要找的element.
|
k*****7
发帖数: 72 | 30 for( i=0; i< 10; i++ )
{
x = B[i];
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}
这个太牛了~~~醍醐灌顶啊 |
|
|
m**q
发帖数: 189 | 31 明白你说的意思了，但还是没有映射到代码上去
为什么用 twos |= x & ones 就能把x加到twos里面去了呢？
【在 M*****e 的大作中提到】
: 这个变量名已经说得很明确了，
: ones就是所有出现过一次的，所以每次更新用xor （注意后面去除了三次的）。
: twos就是出现过两次的，更新的意思就是如果当前数b[i]在ones中存在, b[i]&ones，
: 就加到twos里面。
: three就是一次和两次都出现过的，所以要从ones和twos中每次去除, & not_threes
|
s*****y
发帖数: 897 | |
g*****n
发帖数: 216 | 33 quick sort and use rank information
【在 s******e 的大作中提到】
: 数组中有1个数出现一次，其他数出现三次，怎么求出这个出现1次的数
: 求不用额外内存的O(n)的方法，谢谢
: 可以constant的内存
|
i****s
发帖数: 1152 | 34 how about this case
1,5,5,5,7,7,7,11,11,11
1 - 1
5 - 101
5 - 101
5 - 101
7 - 111
7 - 111
7 - 111
11 - 1011
11 - 1011
11 - 1011
the bit-wise sum value turns to be 3660. mod 3 ends up with 0.
【在 s*****y 的大作中提到】
: sorry. The mod operaton is for each bit position, not for the sum.
: So it is really tricky to code the problem in this way.
: 163 is 1mode3 6mod3 3mod3 so result is 100.
|
s*****t
发帖数: 987 | 35
他的意思应该是把这个都加起来，不算进位的，最后一位加在一起是10，然后mod 3就
会是1
【在 i****s 的大作中提到】
: how about this case
: 1,5,5,5,7,7,7,11,11,11
: 1 - 1
: 5 - 101
: 5 - 101
: 5 - 101
: 7 - 111
: 7 - 111
: 7 - 111
: 11 - 1011
|
i****s
发帖数: 1152 | 36 直接转3进制，bitwise sum 不进位应该更好一些吧.
【在 s*****t 的大作中提到】
:
: 他的意思应该是把这个都加起来，不算进位的，最后一位加在一起是10，然后mod 3就
: 会是1
|
l*****g
发帖数: 685 | 37 这个方法需要O(n)的额外空间吧
【在 a****s 的大作中提到】
: 用quicksort 的idea, 找一个pivot, 然后partition, 扔掉有3n个elements 的
: partition, 如果两个partition都有3n个elements, 那么pivot就是要找的element.
|
l*****g
发帖数: 685 | 38 cool
而且这个可以很简洁地推广到有n个相同元素的问题
【在 r*****l 的大作中提到】
: 所有数转换成三进制。
: 1，每个数个位相加，取结果最低位，作为个位。
: 2，每个数十位相加，取结果最低位，作为十位。
: 。。。
: 然后再转成10进制。
: 20,3,3,3,7,7,7
: 20 - 202 (三进制)
: 3 - 10
: 3 - 10
: 3 - 10
|
g**e
发帖数: 6127 | 39 我觉得这种方法不是constant space，跟最大数转换成n进制之后的位数有关
【在 l*****g 的大作中提到】
: cool
: 而且这个可以很简洁地推广到有n个相同元素的问题
|
l*****g
发帖数: 685 | 40 n进制中的n对于这个问题来说应该算常量
变量是array中的元素数目
【在 g**e 的大作中提到】
: 我觉得这种方法不是constant space，跟最大数转换成n进制之后的位数有关
|
|
|
r*****e
发帖数: 792 | 41 How to apply the careercup method if the given array
has only one number appearing once, some twice and
some three times?
Cannot think of a bit-wise based way to find the only
number by reading the array only one time.
Thanks for giving your thoughts. |
