d**e
发帖数: 6098 | 1 刚面完，就一题，我太弱了，刚好做完，还要他提示
正数数组，未排序，删除重复的。不能排序再删。
用HashSet写完，人家说okay，但希望不要用Set. |
h****n
发帖数: 1093 | 2 两个嵌套的loop即可。。然后人家问你你在用hashset优化 |
d**e
发帖数: 6098 | 3 我觉得第一感觉肯定是用set做的，很难第一时间就用两个loop做O(n^2)
【在 h****n 的大作中提到】
: 两个嵌套的loop即可。。然后人家问你你在用hashset优化
|
a*******y
发帖数: 1040 | 4 这题要是直接用O（n^2)才傻吧，或者他向你用bitvector？
【在 d**e 的大作中提到】
: 刚面完，就一题，我太弱了，刚好做完，还要他提示
: 正数数组，未排序，删除重复的。不能排序再删。
: 用HashSet写完，人家说okay，但希望不要用Set.
|
p*****2
发帖数: 21240 | |
d**e
发帖数: 6098 | 6 的确是，但未能完全达到他的要求。
我就直接new了一个bit array,长度为最大整数
他提示先扫描得到range，就可以相对小的的array，当然worst case还是最大整数
【在 a*******y 的大作中提到】
: 这题要是直接用O（n^2)才傻吧，或者他向你用bitvector？
|
d**e
发帖数: 6098 | 7 返回新数组，重复元素取第一个
【在 p*****2 的大作中提到】
: 数组怎么删除呀？把重复的元素变为0？
|
p*****2
发帖数: 21240 | 8
不是inplace呀？
【在 d**e 的大作中提到】
: 返回新数组，重复元素取第一个
|
p*****2
发帖数: 21240 | 9
面试管有问题吧？
【在 d**e 的大作中提到】
: 的确是，但未能完全达到他的要求。
: 我就直接new了一个bit array,长度为最大整数
: 他提示先扫描得到range，就可以相对小的的array，当然worst case还是最大整数
|
j******2
发帖数: 362 | 10 扫第一遍，get range，用个bitvector当flag, cover range。
扫第二遍，把flag填好。根据flag里1的个数建个新数组。
扫第三遍，按照顺序把新数组填满unique numbers
O(n)
是这意思吧？ |
|
|
a*******y
发帖数: 1040 | 11 为啥扫描这么多
你32位的也就2^32/8 个byte，内存还不到1Mb
【在 j******2 的大作中提到】
: 扫第一遍，get range，用个bitvector当flag, cover range。
: 扫第二遍，把flag填好。根据flag里1的个数建个新数组。
: 扫第三遍，按照顺序把新数组填满unique numbers
: O(n)
: 是这意思吧？
|
d**e
发帖数: 6098 | 12 yes, almost what he needed.
【在 j******2 的大作中提到】
: 扫第一遍，get range，用个bitvector当flag, cover range。
: 扫第二遍，把flag填好。根据flag里1的个数建个新数组。
: 扫第三遍，按照顺序把新数组填满unique numbers
: O(n)
: 是这意思吧？
|
d**e
发帖数: 6098 | 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
|
d**e
发帖数: 6098 | 14 inplace is not required.
if a inplace method exists, i don't think it would be easy.
【在 p*****2 的大作中提到】
:
: 面试管有问题吧？
|
p*****2
发帖数: 21240 | 15
真牛。
【在 a*******y 的大作中提到】
: 为啥扫描这么多
: 你32位的也就2^32/8 个byte，内存还不到1Mb
|
e***s
发帖数: 799 | 16 不是应该512MB吗？
【在 a*******y 的大作中提到】
: 为啥扫描这么多
: 你32位的也就2^32/8 个byte，内存还不到1Mb
|
h****n
发帖数: 1093 | 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 的大作中提到】
: 返回新数组，重复元素取第一个
|
a*******y
发帖数: 1040 | |
d**e
发帖数: 6098 | 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
|
e***s
发帖数: 799 | 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
|
|
|
g**e
发帖数: 6127 | 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
|
h****n
发帖数: 1093 | 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
|
d**e
发帖数: 6098 | 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?
|
j******2
发帖数: 362 | 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
|
l****c
发帖数: 782 | 25 谁能回答我一个弱问啊？
在C++里面，用unordered_map做这道题的时候，应该用related int AS the key吧？那
在hashtable里面存的什么呢？unordered_map不是两个elements吗？一个key，另一个
是啥呢？谢谢。 |
g****y
发帖数: 240 | 26 用set 就好了吧，不用map
【在 l****c 的大作中提到】
: 谁能回答我一个弱问啊？
: 在C++里面，用unordered_map做这道题的时候，应该用related int AS the key吧？那
: 在hashtable里面存的什么呢？unordered_map不是两个elements吗？一个key，另一个
: 是啥呢？谢谢。
|
l****c
发帖数: 782 | 27 谢谢，但是还是O(1)的吗？
【在 g****y 的大作中提到】
: 用set 就好了吧，不用map
|
a*******y
发帖数: 1040 | 28 No, set is a binary tree which is O(logn),就用unordered——map好了
【在 l****c 的大作中提到】
: 谢谢，但是还是O(1)的吗？
|
l****c
发帖数: 782 | 29 我在想可不可以用unordered_set
【在 a*******y 的大作中提到】
: No, set is a binary tree which is O(logn),就用unordered——map好了
|
a*******y
发帖数: 1040 | 30 这题坚持用set的原因是啥？就是因为set是unique的原因？那我要是面试官我也不高兴啊
【在 l****c 的大作中提到】
: 我在想可不可以用unordered_set
|
|
|
l****c
发帖数: 782 | 31 你用map，second存啥呢
兴啊
【在 a*******y 的大作中提到】
: 这题坚持用set的原因是啥？就是因为set是unique的原因？那我要是面试官我也不高兴啊
|
a*******y
发帖数: 1040 | 32 count
【在 l****c 的大作中提到】
: 你用map，second存啥呢
:
: 兴啊
|
l****c
发帖数: 782 | 33 能够不需要count解，为什么非要存个count
【在 a*******y 的大作中提到】
: count
|
a*******y
发帖数: 1040 | 34 要是吧这题改成让你implement a hashset你估计就爽了，要不你写下吧，这个也是常
见题
【在 l****c 的大作中提到】
: 能够不需要count解，为什么非要存个count
|
l****c
发帖数: 782 | 35 我是真心求教
【在 a*******y 的大作中提到】
: 要是吧这题改成让你implement a hashset你估计就爽了，要不你写下吧，这个也是常
: 见题
|
