问一道排序题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

问一道排序题目

问一道排序题目# Programming - 葵花宝典

u*c2006-12-09 08:12

1 楼

有一个已经排好序的数组，其中有些重复的元素，比如{1,1,1,2,3,3,4,5,5}.现在
要把这个数组变成{1,2,3,4,5,1,3,5,1},也就是每个序列都是有序的且其中的元素
唯一，有没有好的算法。只能使用O(1)的辅助空间。
O(n^2)的算法是很显然的。

P*f2006-12-09 08:12

2 楼

难道不是一遍扫描O(n)?
两个index positions 分别指向就绪数组地插入位置和新candidate元素的检查位置

有一个已经排好序的数组，其中有些重复的元素，比如{1,1,1,2,3,3,4,5,5}.现在
要把这个数组变成{1,2,3,4,5,1,3,5,1},也就是每个序列都是有序的且其中的元素
唯一，有没有好的算法。只能使用O(1)的辅助空间。
O(n^2)的算法是很显然的。

【在 u*c 的大作中提到】

: 有一个已经排好序的数组，其中有些重复的元素，比如{1,1,1,2,3,3,4,5,5}.现在
: 要把这个数组变成{1,2,3,4,5,1,3,5,1},也就是每个序列都是有序的且其中的元素
: 唯一，有没有好的算法。只能使用O(1)的辅助空间。
: O(n^2)的算法是很显然的。

t*t2006-12-09 08:12

3 楼

数组不好插入吧,如果是双链表就没问题.但是已经说了不许换空间了.

【在 P*****f 的大作中提到】

: 难道不是一遍扫描O(n)?
: 两个index positions 分别指向就绪数组地插入位置和新candidate元素的检查位置
:
: 有一个已经排好序的数组，其中有些重复的元素，比如{1,1,1,2,3,3,4,5,5}.现在
: 要把这个数组变成{1,2,3,4,5,1,3,5,1},也就是每个序列都是有序的且其中的元素
: 唯一，有没有好的算法。只能使用O(1)的辅助空间。
: O(n^2)的算法是很显然的。

c*d2006-12-09 08:12

4 楼

O(1)没问题。一次只需要换一个元素，就在原来的数组上操作。

【在 t****t 的大作中提到】

: 数组不好插入吧,如果是双链表就没问题.但是已经说了不许换空间了.

s*e2006-12-09 08:12

5 楼

换到哪儿去?

【在 c***d 的大作中提到】

: O(1)没问题。一次只需要换一个元素，就在原来的数组上操作。

k*f2006-12-09 08:12

6 楼

换到最后去，做一次旋转，
i,i+1,..n, --> i+1,i+2,...,n,i
不过，得要n^2复杂度

【在 s***e 的大作中提到】

: 换到哪儿去?

P*f2006-12-09 08:12

7 楼

我这个就绪数组是指原数组得已处理好部分
我觉得这题关键就是找准一个loop invariant

数组不好插入吧,如果是双链表就没问题.但是已经说了不许换空间了.

【在 t****t 的大作中提到】

: 数组不好插入吧,如果是双链表就没问题.但是已经说了不许换空间了.

c*d2006-12-09 08:12

8 楼

thrust is right. If link list, insertion is O(1), thus overall complexity O(
n). If array, insertion is O(n), over all complexity is n square.
but no matter what, only O(1) extra space is needed.

【在 s***e 的大作中提到】

: 换到哪儿去?

P*f2006-12-09 08:12

9 楼

why o(n) for a single insert in case of array?
could you please give a counter example?
I think when you insert one element, just overlap the previous repeated
element.
no need to move.

O(

【在 c***d 的大作中提到】

: thrust is right. If link list, insertion is O(1), thus overall complexity O(
: n). If array, insertion is O(n), over all complexity is n square.
: but no matter what, only O(1) extra space is needed.

P*f2006-12-09 08:12

10 楼

en, I misunderstand the problem. forget it.

why o(n) for a single insert in case of array?
could you please give a counter example?
I think when you insert one element, just overlap the previous repeated
element.
no need to move.
O(

【在 P*****f 的大作中提到】

: why o(n) for a single insert in case of array?
: could you please give a counter example?
: I think when you insert one element, just overlap the previous repeated
: element.
: no need to move.
:
: O(

P*f2006-12-09 08:12

11 楼

这个结果是确定的么？是否要求子序列最长？
比如给定 1 1 1 2 2 3 3 5
生成1 2 1 2 1 3 5 3满足"sub sequence is ordered and no element repetition"
but the length of sub sequence is not maximium.
if this is acceptable, seems like we can apply swap based algorithm.

有一个已经排好序的数组，其中有些重复的元素，比如{1,1,1,2,3,3,4,5,5}.现在
要把这个数组变成{1,2,3,4,5,1,3,5,1},也就是每个序列都是有序的且其中的元素
唯一，有没有好的算法。只能使用O(1)的辅助空间。
O(n^2)的算法是很显然的。

【在 u*c 的大作中提到】

a*e2006-12-09 08:12

12 楼

An O(n log n) algorithm:
1. Let b = 1+ the max value (the last one in sequence);
2. Add b^i to the ith (zero based indexing) repeated element;
3. Sort the sequence as usual;
4. Recover the original sequence.

【在 u*c 的大作中提到】

s*e2006-12-09 08:12

13 楼

emmm, very nice

【在 a*******e 的大作中提到】

: An O(n log n) algorithm:
: 1. Let b = 1+ the max value (the last one in sequence);
: 2. Add b^i to the ith (zero based indexing) repeated element;
: 3. Sort the sequence as usual;
: 4. Recover the original sequence.

P*f2006-12-09 08:12

14 楼

good, just a littile bit concern of overflow:)

An O(n log n) algorithm:
1. Let b = 1+ the max value (the last one in sequence);
2. Add b^i to the ith (zero based indexing) repeated element;
3. Sort the sequence as usual;
4. Recover the original sequence.

【在 a*******e 的大作中提到】

g*c2006-12-09 08:12

15 楼

special case will overflow
here is mine idea
do runlength coding and special decoding to construct the required sequence.
coding O(n), decoding time complexity average/best caseO(n), I think 2*O(b)～=
O(1) space for runlength need if b is constant.
worst case is tricky, it looks like O(b*(n-b)), could achive O(n) in double for
loops.

【在 a*******e 的大作中提到】

u*c2006-12-09 08:12

16 楼

每个序列都是剩下的元素中所能找到的最长的有序序列。

【在 P*****f 的大作中提到】

: 这个结果是确定的么？是否要求子序列最长？
: 比如给定 1 1 1 2 2 3 3 5
: 生成1 2 1 2 1 3 5 3满足"sub sequence is ordered and no element repetition"
: but the length of sub sequence is not maximium.
: if this is acceptable, seems like we can apply swap based algorithm.
:
: 有一个已经排好序的数组，其中有些重复的元素，比如{1,1,1,2,3,3,4,5,5}.现在
: 要把这个数组变成{1,2,3,4,5,1,3,5,1},也就是每个序列都是有序的且其中的元素
: 唯一，有没有好的算法。只能使用O(1)的辅助空间。
: O(n^2)的算法是很显然的。

d*g2006-12-09 08:12

17 楼

since only O(1) space is given, it is actually a hint: using swap
1. i = 1; (skip the first one, i == 0 )
*2. if a(i) <= a(i-1), find next one a(j) which is the first one that is
greater than a(i-1)
3. swap a(i) and a(j)
4. i ++, go to step 2 until i reaches the end of the array
*where in step 2, on the way to find the right a(j), if there is one element
a(m) which is equal to a(i-1) (thus greater than a(i)), put a(i) value to
index m, and use the value of a(m) to continue to find the right a(j)

t*t2006-12-09 08:12

18 楼

你这个是O(n)吗?

element
then
to

【在 d***g 的大作中提到】

: since only O(1) space is given, it is actually a hint: using swap
: 1. i = 1; (skip the first one, i == 0 )
: *2. if a(i) <= a(i-1), find next one a(j) which is the first one that is
: greater than a(i-1)
: 3. swap a(i) and a(j)
: 4. i ++, go to step 2 until i reaches the end of the array
: *where in step 2, on the way to find the right a(j), if there is one element
: a(m) which is equal to a(i-1) (thus greater than a(i)), put a(i) value to
: index m, and use the value of a(m) to continue to find the right a(j)

c*d2006-12-09 08:12

19 楼

that algorithm is O(n), but wont work. Since simply swap a[i] and a[j] will
mess up the order.

【在 t****t 的大作中提到】

: 你这个是O(n)吗?
:
: element
: then
: to

P*t2006-12-09 08:12

20 楼

Cool! b * i 也可以吧！减少一点OVERFLOW的机会。

【在 a*******e 的大作中提到】

t*o2006-12-09 08:12

21 楼

hmmm, 改得不错.

【在 P***t 的大作中提到】

: Cool! b * i 也可以吧！减少一点OVERFLOW的机会。

t*o2006-12-09 08:12

22 楼

adumbrare 的code group是指数间距, 有OVERFLOW 的可能性。你的间距是线性的，
OVERFLOW的机会大大减小。我再改一下，间距为1，OVERFLOW的机会就更小些。
还是coding的思路,但不再用整数，而是用字符串：
1. add i_ prefix to the ith (zero based indexing) repeated element,
e.g., 1 1 2 3 3->0_1 1_1 0_2 0_3 1_3
2. sort the sequence in ascending order;
3. remove the prefix.

【在 P***t 的大作中提到】

: Cool! b * i 也可以吧！减少一点OVERFLOW的机会。

k*k2006-12-09 08:12

23 楼

this is not O(1) extra space bah..

【在 t***o 的大作中提到】

: adumbrare 的code group是指数间距, 有OVERFLOW 的可能性。你的间距是线性的，
: OVERFLOW的机会大大减小。我再改一下，间距为1，OVERFLOW的机会就更小些。
: 还是coding的思路,但不再用整数，而是用字符串：
: 1. add i_ prefix to the ith (zero based indexing) repeated element,
: e.g., 1 1 2 3 3->0_1 1_1 0_2 0_3 1_3
: 2. sort the sequence in ascending order;
: 3. remove the prefix.