d*e
1 楼
刚面完，就一题，我太弱了，刚好做完，还要他提示
正数数组，未排序，删除重复的。不能排序再删。
用HashSet写完，人家说okay，但希望不要用Set.
正数数组，未排序，删除重复的。不能排序再删。
用HashSet写完，人家说okay，但希望不要用Set.
h*n
2 楼
两个嵌套的loop即可。。然后人家问你你在用hashset优化
d*e
3 楼
我觉得第一感觉肯定是用set做的，很难第一时间就用两个loop做O(n^2)
【在 h****n 的大作中提到】
: 两个嵌套的loop即可。。然后人家问你你在用hashset优化
【在 h****n 的大作中提到】
: 两个嵌套的loop即可。。然后人家问你你在用hashset优化
a*y
4 楼
这题要是直接用O（n^2)才傻吧，或者他向你用bitvector？
【在 d**e 的大作中提到】
: 刚面完，就一题，我太弱了，刚好做完，还要他提示
: 正数数组，未排序，删除重复的。不能排序再删。
: 用HashSet写完，人家说okay，但希望不要用Set.
【在 d**e 的大作中提到】
: 刚面完，就一题，我太弱了，刚好做完，还要他提示
: 正数数组，未排序，删除重复的。不能排序再删。
: 用HashSet写完，人家说okay，但希望不要用Set.
p*2
5 楼
数组怎么删除呀？把重复的元素变为0？
d*e
6 楼
的确是，但未能完全达到他的要求。
我就直接new了一个bit array,长度为最大整数
他提示先扫描得到range，就可以相对小的的array，当然worst case还是最大整数
【在 a*******y 的大作中提到】
: 这题要是直接用O（n^2)才傻吧，或者他向你用bitvector？
我就直接new了一个bit array,长度为最大整数
他提示先扫描得到range，就可以相对小的的array，当然worst case还是最大整数
【在 a*******y 的大作中提到】
: 这题要是直接用O（n^2)才傻吧，或者他向你用bitvector？
d*e
7 楼
返回新数组，重复元素取第一个
【在 p*****2 的大作中提到】
: 数组怎么删除呀？把重复的元素变为0？
【在 p*****2 的大作中提到】
: 数组怎么删除呀？把重复的元素变为0？
p*2
8 楼
不是inplace呀？
【在 d**e 的大作中提到】
: 返回新数组，重复元素取第一个
p*2
9 楼
面试管有问题吧？
【在 d**e 的大作中提到】
: 的确是，但未能完全达到他的要求。
: 我就直接new了一个bit array,长度为最大整数
: 他提示先扫描得到range，就可以相对小的的array，当然worst case还是最大整数
j*2
10 楼
扫第一遍，get range，用个bitvector当flag, cover range。
扫第二遍，把flag填好。根据flag里1的个数建个新数组。
扫第三遍，按照顺序把新数组填满unique numbers
O(n)
是这意思吧？
扫第二遍，把flag填好。根据flag里1的个数建个新数组。
扫第三遍，按照顺序把新数组填满unique numbers
O(n)
是这意思吧？
a*y
11 楼
为啥扫描这么多
你32位的也就2^32/8 个byte，内存还不到1Mb
【在 j******2 的大作中提到】
: 扫第一遍，get range，用个bitvector当flag, cover range。
: 扫第二遍，把flag填好。根据flag里1的个数建个新数组。
: 扫第三遍，按照顺序把新数组填满unique numbers
: O(n)
: 是这意思吧？
你32位的也就2^32/8 个byte，内存还不到1Mb
【在 j******2 的大作中提到】
: 扫第一遍，get range，用个bitvector当flag, cover range。
: 扫第二遍，把flag填好。根据flag里1的个数建个新数组。
: 扫第三遍，按照顺序把新数组填满unique numbers
: O(n)
: 是这意思吧？
d*e
12 楼
yes, almost what he needed.
【在 j******2 的大作中提到】
: 扫第一遍，get range，用个bitvector当flag, cover range。
: 扫第二遍，把flag填好。根据flag里1的个数建个新数组。
: 扫第三遍，按照顺序把新数组填满unique numbers
: O(n)
: 是这意思吧？
【在 j******2 的大作中提到】
: 扫第一遍，get range，用个bitvector当flag, cover range。
: 扫第二遍，把flag填好。根据flag里1的个数建个新数组。
: 扫第三遍，按照顺序把新数组填满unique numbers
: O(n)
: 是这意思吧？
d*e
13 楼
he required not to use a 2^32 array, as the element might be from 1 to 100,
although the worst case is 2^32...
【在 a*******y 的大作中提到】
: 为啥扫描这么多
: 你32位的也就2^32/8 个byte，内存还不到1Mb
although the worst case is 2^32...
【在 a*******y 的大作中提到】
: 为啥扫描这么多
: 你32位的也就2^32/8 个byte，内存还不到1Mb
d*e
14 楼
inplace is not required.
if a inplace method exists, i don't think it would be easy.
【在 p*****2 的大作中提到】
:
: 面试管有问题吧？
if a inplace method exists, i don't think it would be easy.
【在 p*****2 的大作中提到】
:
: 面试管有问题吧？
p*2
15 楼
真牛。
【在 a*******y 的大作中提到】
: 为啥扫描这么多
: 你32位的也就2^32/8 个byte，内存还不到1Mb
e*s
16 楼
不是应该512MB吗？
【在 a*******y 的大作中提到】
: 为啥扫描这么多
: 你32位的也就2^32/8 个byte，内存还不到1Mb
【在 a*******y 的大作中提到】
: 为啥扫描这么多
: 你32位的也就2^32/8 个byte，内存还不到1Mb
h*n
17 楼
Then the bitvector method cannot work.
You should keep the order of element in the original array.
For example,
4 3 3 6 6 2 7 7 1
You need to get 4 3 6 2 7 1
Using bitvector, you only get 1 2 3 4 6 7
【在 d**e 的大作中提到】
: 返回新数组，重复元素取第一个
You should keep the order of element in the original array.
For example,
4 3 3 6 6 2 7 7 1
You need to get 4 3 6 2 7 1
Using bitvector, you only get 1 2 3 4 6 7
【在 d**e 的大作中提到】
: 返回新数组，重复元素取第一个
a*y
18 楼
hehe ,type, 1G
d*e
19 楼
don't scan the bitvector, you can do this:
for e in input_array
if bitvector(e) is 1 then
append e to result
set bitvector(e) to 0
end if
end for
【在 h****n 的大作中提到】
: Then the bitvector method cannot work.
: You should keep the order of element in the original array.
: For example,
: 4 3 3 6 6 2 7 7 1
: You need to get 4 3 6 2 7 1
: Using bitvector, you only get 1 2 3 4 6 7
for e in input_array
if bitvector(e) is 1 then
append e to result
set bitvector(e) to 0
end if
end for
【在 h****n 的大作中提到】
: Then the bitvector method cannot work.
: You should keep the order of element in the original array.
: For example,
: 4 3 3 6 6 2 7 7 1
: You need to get 4 3 6 2 7 1
: Using bitvector, you only get 1 2 3 4 6 7
e*s
20 楼
为什么？bitvector只用来查看数字是否存在不可以吗？
是不是应该把情况问清楚，如果，数字都是1 ~ 100而且不是很多，可以先扫一遍得到
range。 如果数组个数很多，先扫一遍是不是很影响效率呢？
【在 h****n 的大作中提到】
: Then the bitvector method cannot work.
: You should keep the order of element in the original array.
: For example,
: 4 3 3 6 6 2 7 7 1
: You need to get 4 3 6 2 7 1
: Using bitvector, you only get 1 2 3 4 6 7
是不是应该把情况问清楚，如果，数字都是1 ~ 100而且不是很多，可以先扫一遍得到
range。 如果数组个数很多，先扫一遍是不是很影响效率呢？
【在 h****n 的大作中提到】
: Then the bitvector method cannot work.
: You should keep the order of element in the original array.
: For example,
: 4 3 3 6 6 2 7 7 1
: You need to get 4 3 6 2 7 1
: Using bitvector, you only get 1 2 3 4 6 7
g*e
21 楼
我最近面试老问排序in place去重
以后也可以问问你这题
【在 d**e 的大作中提到】
: don't scan the bitvector, you can do this:
: for e in input_array
: if bitvector(e) is 1 then
: append e to result
: set bitvector(e) to 0
: end if
: end for
以后也可以问问你这题
【在 d**e 的大作中提到】
: don't scan the bitvector, you can do this:
: for e in input_array
: if bitvector(e) is 1 then
: append e to result
: set bitvector(e) to 0
: end if
: end for
h*n
22 楼
Well, I see.
But this method seems to be just a simplified version of HashSet, doesn't it?
【在 d**e 的大作中提到】
: don't scan the bitvector, you can do this:
: for e in input_array
: if bitvector(e) is 1 then
: append e to result
: set bitvector(e) to 0
: end if
: end for
But this method seems to be just a simplified version of HashSet, doesn't it?
【在 d**e 的大作中提到】
: don't scan the bitvector, you can do this:
: for e in input_array
: if bitvector(e) is 1 then
: append e to result
: set bitvector(e) to 0
: end if
: end for
d*e
23 楼
yes... the idea is the same...
i thought what he wanted to know was
1) if i can code
2) if i know HashSet
3) if i know bitvector
it?
【在 h****n 的大作中提到】
: Well, I see.
: But this method seems to be just a simplified version of HashSet, doesn't it?
i thought what he wanted to know was
1) if i can code
2) if i know HashSet
3) if i know bitvector
it?
【在 h****n 的大作中提到】
: Well, I see.
: But this method seems to be just a simplified version of HashSet, doesn't it?
j*2
24 楼
所以还是要扫三遍是不
【在 d**e 的大作中提到】
: don't scan the bitvector, you can do this:
: for e in input_array
: if bitvector(e) is 1 then
: append e to result
: set bitvector(e) to 0
: end if
: end for
【在 d**e 的大作中提到】
: don't scan the bitvector, you can do this:
: for e in input_array
: if bitvector(e) is 1 then
: append e to result
: set bitvector(e) to 0
: end if
: end for
l*c
25 楼
谁能回答我一个弱问啊？
在C++里面，用unordered_map做这道题的时候，应该用related int AS the key吧？那
在hashtable里面存的什么呢？unordered_map不是两个elements吗？一个key，另一个
是啥呢？谢谢。
在C++里面，用unordered_map做这道题的时候，应该用related int AS the key吧？那
在hashtable里面存的什么呢？unordered_map不是两个elements吗？一个key，另一个
是啥呢？谢谢。
g*y
26 楼
用set 就好了吧，不用map
【在 l****c 的大作中提到】
: 谁能回答我一个弱问啊？
: 在C++里面，用unordered_map做这道题的时候，应该用related int AS the key吧？那
: 在hashtable里面存的什么呢？unordered_map不是两个elements吗？一个key，另一个
: 是啥呢？谢谢。
【在 l****c 的大作中提到】
: 谁能回答我一个弱问啊？
: 在C++里面，用unordered_map做这道题的时候，应该用related int AS the key吧？那
: 在hashtable里面存的什么呢？unordered_map不是两个elements吗？一个key，另一个
: 是啥呢？谢谢。
l*c
27 楼
谢谢，但是还是O(1)的吗？
【在 g****y 的大作中提到】
: 用set 就好了吧，不用map
【在 g****y 的大作中提到】
: 用set 就好了吧，不用map
a*y
28 楼
No, set is a binary tree which is O(logn),就用unordered——map好了
【在 l****c 的大作中提到】
: 谢谢，但是还是O(1)的吗？
【在 l****c 的大作中提到】
: 谢谢，但是还是O(1)的吗？
l*c
29 楼
我在想可不可以用unordered_set
【在 a*******y 的大作中提到】
: No, set is a binary tree which is O(logn),就用unordered——map好了
【在 a*******y 的大作中提到】
: No, set is a binary tree which is O(logn),就用unordered——map好了
a*y
30 楼
这题坚持用set的原因是啥？就是因为set是unique的原因？那我要是面试官我也不高兴啊
【在 l****c 的大作中提到】
: 我在想可不可以用unordered_set
【在 l****c 的大作中提到】
: 我在想可不可以用unordered_set
l*c
31 楼
你用map，second存啥呢
兴啊
【在 a*******y 的大作中提到】
: 这题坚持用set的原因是啥？就是因为set是unique的原因？那我要是面试官我也不高兴啊
兴啊
【在 a*******y 的大作中提到】
: 这题坚持用set的原因是啥？就是因为set是unique的原因？那我要是面试官我也不高兴啊
a*y
32 楼
count
【在 l****c 的大作中提到】
: 你用map，second存啥呢
:
: 兴啊
【在 l****c 的大作中提到】
: 你用map，second存啥呢
:
: 兴啊
l*c
33 楼
能够不需要count解，为什么非要存个count
【在 a*******y 的大作中提到】
: count
【在 a*******y 的大作中提到】
: count
a*y
34 楼
要是吧这题改成让你implement a hashset你估计就爽了，要不你写下吧，这个也是常
见题
【在 l****c 的大作中提到】
: 能够不需要count解，为什么非要存个count
见题
【在 l****c 的大作中提到】
: 能够不需要count解，为什么非要存个count
l*c
35 楼
我是真心求教
【在 a*******y 的大作中提到】
: 要是吧这题改成让你implement a hashset你估计就爽了，要不你写下吧，这个也是常
: 见题
【在 a*******y 的大作中提到】
: 要是吧这题改成让你implement a hashset你估计就爽了，要不你写下吧，这个也是常
: 见题
相关阅读
有谁愿意花$6500 去这个会？建议给majia同学搞个众筹。纪录片《Abacus: Small Enough to Jail》 (转载)成立华人利益组织征名USA 这些公司会给办eb1b吗？同一个职位要不要继续申请？Therano关门了请问这两个工作哪个比较好 (w2 vs 1099)？工作求助求建议上市公司San Jose 招聘Sr. computer vision加州公司招聘控制工程师求G家Kirkland team matchJob满版的evil manager, EBIZ满版的evil 6i分享一道trading firm的code screen，只能用c++facebook 电面H-1B RFE approved OPT ext pending脸家，选product还是infrastructure请问关于opt时间的计算问题！！牛逼 雅虎美女ceo上任18个月内 女编辑从20% 到了80% (转载)求助！！OPT被deny，因为SEVIS里把学位搞错了