n*******r
发帖数: 22 | 1 实在想不出in-place的方法。哪位提示我一下？ |
A*****i
发帖数: 3587 | 2 用vector
然后用迭代器迭代
以前做file system的时候经常遇到这种问题 |
n*******r
发帖数: 22 | 3 你说的是stl::vector？那还是in-place吗？
【在 A*****i 的大作中提到】
: 用vector
: 然后用迭代器迭代
: 以前做file system的时候经常遇到这种问题
|
D*****7
发帖数: 766 | 4 每碰到一个，就去已经找过的部分看看是不是已经存在，时间复杂度很高
如果对时间复杂度有进一步的要求话，就将已经找过的部分构建成一个BST（用Array来
表达BST）。
【在 n*******r 的大作中提到】
: 实在想不出in-place的方法。哪位提示我一下？
|
k*p
发帖数: 1526 | 5 二重循环，维护tail指针
【在 n*******r 的大作中提到】
: 实在想不出in-place的方法。哪位提示我一下？
|
h**k
发帖数: 3368 | 6 如果允许用额外空间，可以先记录重复字符，然后用两个指针遍历数组。这个遍历类似
于Binary Search中二分数组。
【在 n*******r 的大作中提到】
: 实在想不出in-place的方法。哪位提示我一下？
|
r*******e
发帖数: 7583 | 7 时间复杂度没有要求？
那就in-place sort，然后用两个指针走一遍就好了。。
【在 n*******r 的大作中提到】
: 实在想不出in-place的方法。哪位提示我一下？
|
i**c
发帖数: 26 | 8 你这个"很大的CHAR[]",言外之意要不能一次装入内存?
【在 n*******r 的大作中提到】
: 实在想不出in-place的方法。哪位提示我一下？
|
p******r
发帖数: 2999 | 9 利用bitmap，只需要一个char
【在 n*******r 的大作中提到】
: 实在想不出in-place的方法。哪位提示我一下？
|
j*****u
发帖数: 1133 | 10 允许额外空间不？
void RemoveDuplicates(ref T[] array)
{
var set = new HashSet();
int last = 0;
for (int i = 0; i < array.Length; ++i)
if (set.Add(array[i]))
array[last++] = array[i];
Array.Resize(ref array, last);
}
【在 n*******r 的大作中提到】
: 实在想不出in-place的方法。哪位提示我一下？
|
|
|
j********x
发帖数: 2330 | 11 o了，就这么精妙
【在 p******r 的大作中提到】
: 利用bitmap，只需要一个char
|
f*****w
发帖数: 2602 | 12
为什么？
【在 p******r 的大作中提到】
: 利用bitmap，只需要一个char
|
g***s
发帖数: 3811 | 13 same idea with the question yesterday.
for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
which means it is not a duplicate, swap; otherwise(duplicate), clean.
for the rest, just check/clean.
after the above steps, compact all chars. |
c*********t
发帖数: 2921 | 14 grass,
能不能讲讲你指的”the question yesterday“ 是哪个帖子？
你的方法能不能再讲的具体一点，好像没有领会你的要点。
谢谢！
【在 g***s 的大作中提到】
: same idea with the question yesterday.
: for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
: which means it is not a duplicate, swap; otherwise(duplicate), clean.
: for the rest, just check/clean.
: after the above steps, compact all chars.
|
m**q
发帖数: 189 | 15 grass 你这方法太牛了，最近在板上看到至少三四道可以用这个解的题了...
【在 g***s 的大作中提到】
: same idea with the question yesterday.
: for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
: which means it is not a duplicate, swap; otherwise(duplicate), clean.
: for the rest, just check/clean.
: after the above steps, compact all chars.
|
h*****g
发帖数: 312 | 16 NB!!!!
【在 g***s 的大作中提到】
: same idea with the question yesterday.
: for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
: which means it is not a duplicate, swap; otherwise(duplicate), clean.
: for the rest, just check/clean.
: after the above steps, compact all chars.
|
h*****g
发帖数: 312 | 17 咋搞？
【在 p******r 的大作中提到】
: 利用bitmap，只需要一个char
|
y***n
发帖数: 1594 | 18 why 256 ?
a[a[i]]!=a[i],
【在 g***s 的大作中提到】
: same idea with the question yesterday.
: for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
: which means it is not a duplicate, swap; otherwise(duplicate), clean.
: for the rest, just check/clean.
: after the above steps, compact all chars.
|
d*******l
发帖数: 338 | 19 这是哪个题啊，好象跟这个帖子讨论的不太一样？倒是跟我以前见过的有点像。。
这个帖子的题我觉得bitmap方法就很好了
【在 y***n 的大作中提到】
: why 256 ?
:
: a[a[i]]!=a[i],
|
g**e
发帖数: 6127 | 20 should check the first 65535 items?
【在 y***n 的大作中提到】
: why 256 ?
:
: a[a[i]]!=a[i],
|
|
|
y***n
发帖数: 1594 | 21 Because Unicode?
【在 g**e 的大作中提到】
: should check the first 65535 items?
|
s**x
发帖数: 7506 | 22 没看懂。 only process first 256?
clean? clean what?
swap? what the loop start after swap? start next position or the current
position need to be checked again with the swapped char?
【在 g***s 的大作中提到】
: same idea with the question yesterday.
: for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
: which means it is not a duplicate, swap; otherwise(duplicate), clean.
: for the rest, just check/clean.
: after the above steps, compact all chars.
|
g**e
发帖数: 6127 | 23 yes
【在 y***n 的大作中提到】
: Because Unicode?
|
f****4
发帖数: 1359 | 24 这个才是正解；而不是256
【在 g**e 的大作中提到】
: should check the first 65535 items?
|
f****4
发帖数: 1359 | 25 1 10 100
下标越界
【在 g***s 的大作中提到】
: same idea with the question yesterday.
: for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
: which means it is not a duplicate, swap; otherwise(duplicate), clean.
: for the rest, just check/clean.
: after the above steps, compact all chars.
|
g***s
发帖数: 3811 | 26 hehe. i just gave the idea. I assumed char.length is large than 256.
【在 f****4 的大作中提到】
: 1 10 100
: 下标越界
|
p*****a
发帖数: 147 | 27 This seems not necessary. a bit map of size 256bits would do the simple
check of duplicate or not. (assuming ascii codes here).
【在 g***s 的大作中提到】
: same idea with the question yesterday.
: for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
: which means it is not a duplicate, swap; otherwise(duplicate), clean.
: for the rest, just check/clean.
: after the above steps, compact all chars.
|
y***n
发帖数: 1594 | 28 so 256 is non-unicode
【在 g**e 的大作中提到】
: yes
|
g***s
发帖数: 3811 | 29 i see. but 'in-place' in the question.
【在 p*****a 的大作中提到】
: This seems not necessary. a bit map of size 256bits would do the simple
: check of duplicate or not. (assuming ascii codes here).
|
e******0
发帖数: 211 | 30 a[a[i]] != a[i]
这没看懂啊
为这么这不是duplicate?
【在 g***s 的大作中提到】
: same idea with the question yesterday.
: for first 256 items, a[i], loop check the position a[i], if a[a[i]]!=a[i],
: which means it is not a duplicate, swap; otherwise(duplicate), clean.
: for the rest, just check/clean.
: after the above steps, compact all chars.
|
|
|
f****4
发帖数: 1359 | 31 那个idea只是在连续整数差一个，两个的情况下才比较合适
这里套的话不合适：题目没说char[]放的东西连续
并且要求in-place，那么用bitmap应该也是不合要求的（？？）
如果能放进内存，可以用变形的quicksort来做
Partition好之后
a[0]x a[i+2]>x ..
. a[j]>x
交换 a[j]<=>a[i]; a[j-1]<=>a[i-1]...a[j-k+2]<=>a[i-k+2]
设置j=j-k+1 (重复的元素被交换到了数组尾部，并且不再参与下一次的递归)
继续
最后得到的数组即为无重复数组+尾部所有的重复元素
将重复元素清空即可
【在 g***s 的大作中提到】
: hehe. i just gave the idea. I assumed char.length is large than 256.
|
g***s
发帖数: 3811 | 32 你没有很好的理解。多考古。
a[i+2]>x ..
【在 f****4 的大作中提到】
: 那个idea只是在连续整数差一个，两个的情况下才比较合适
: 这里套的话不合适：题目没说char[]放的东西连续
: 并且要求in-place，那么用bitmap应该也是不合要求的（？？）
: 如果能放进内存，可以用变形的quicksort来做
: Partition好之后
: a[0]x a[i+2]>x ..
: . a[j]>x
: 交换 a[j]<=>a[i]; a[j-1]<=>a[i-1]...a[j-k+2]<=>a[i-k+2]
: 设置j=j-k+1 (重复的元素被交换到了数组尾部，并且不再参与下一次的递归)
: 继续
|
f****4
发帖数: 1359 | 33 好像不用考古吧
那个a[a[i]] == a[i]的办法，只要给这么个例子就不work了
int a[]={200,1000,10000};
【在 g***s 的大作中提到】
: 你没有很好的理解。多考古。
:
: a[i+2]>x ..
|
f****4
发帖数: 1359 | 34 也不需要变形的quicksort这么复杂，直接quicksort后再走一遍即可 |
g***s
发帖数: 3811 | 35 1. char的范围是-127到127. 具体实现的时候转换成0到256
2. 我前面已经说了，假设length>255
3. 这个方法不是只能用在却一两个数的情况下
4. 我只是给个大概的方向，具体实现可以考古。
【在 f****4 的大作中提到】
: 好像不用考古吧
: 那个a[a[i]] == a[i]的办法，只要给这么个例子就不work了
: int a[]={200,1000,10000};
|
f****4
发帖数: 1359 | 36 -127~127是ascii编码，char* 支持utf8
a[a[i]]==a[i]的确支持int a[10001]={10,100,10000};但必须有假设a足够大>=10001
（这个面试的人能同意么？特别是我给的这个情况）
我想强调的是，这个题目很多限制不确定，a[a[i]]==a[i]不一定能套上
【在 g***s 的大作中提到】
: 1. char的范围是-127到127. 具体实现的时候转换成0到256
: 2. 我前面已经说了，假设length>255
: 3. 这个方法不是只能用在却一两个数的情况下
: 4. 我只是给个大概的方向，具体实现可以考古。
|
g***s
发帖数: 3811 | 37 题目都说了是char[]. 结果你改成int[]. 按你的理解，还要先把char[]里面多位合并
成一位来做？你要这么专我也没啥好说的了。
10001
【在 f****4 的大作中提到】
: -127~127是ascii编码，char* 支持utf8
: a[a[i]]==a[i]的确支持int a[10001]={10,100,10000};但必须有假设a足够大>=10001
: （这个面试的人能同意么？特别是我给的这个情况）
: 我想强调的是，这个题目很多限制不确定，a[a[i]]==a[i]不一定能套上
|
f****4
发帖数: 1359 | 38 我用int a[]举例是因为我不知道怎么输入utf8字符
我上面也说了，char *支持utf8，这个题目很多限制不确定，不是a[a[i]]==a[i]就一
定能套上去的
【在 g***s 的大作中提到】
: 题目都说了是char[]. 结果你改成int[]. 按你的理解，还要先把char[]里面多位合并
: 成一位来做？你要这么专我也没啥好说的了。
:
: 10001
|
g**e
发帖数: 6127 | 39 太nice啦，点到为止就行了
【在 g***s 的大作中提到】
: 题目都说了是char[]. 结果你改成int[]. 按你的理解，还要先把char[]里面多位合并
: 成一位来做？你要这么专我也没啥好说的了。
:
: 10001
|
