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你估计就爽了，要不你写下吧，这个也是常
: 见题
相关阅读
搞了小半个月，leetcode还有20题我来说一下苹果请教版上苹果家的大大每天都收到猎头的信（Linkedin），大家怎么处理？如何做LeetCode想海归广州的看过来--广发银行总行招风险经理 (转载)菜鸟问一道java题目，check balanced binary treeB家電面请问有了解Marlabs这个公司的么关于leetcode请教二爷什么是面试题的“代码质量”？招聘:Mechanical Engineer R&D, 休斯顿-油服公司大家研究一下除了做leetcode怎么能更上一层楼两道简单的面试题浙江大学招收力学与材料方向博士后哪些公司不需要ONSITEAmazon HR 这是啥意思新人问题，本JobHunting版是IT专版么？google intern一般多久出结果啊？OPT才开始用，需要申请今年的h1b吗？