g*****u
发帖数: 298 | 1 S1是1个n个integer(1,2,3,...n)的permutation。现只给你一个integer的缓冲空间，
要求S1变成S2（另一个permutation）。要求O(nlgn)。 | g*****u
发帖数: 298 | 2 不是啊，比如S1=45312，S2=12435。要求in place。 | c*****o
发帖数: 178 | 3 可不可以这样考虑呢，s2 = 12435, s2[1] = 1,s2[2] = 2,s2[3] = 4, s[4] = 3, s2[
5] = 5.在s1= 45312找到相对元素位置, s1[4] = 1, s1[5]= 2, s1[1] = 4, s1[3] =
3, s1[2] = 5. 问题就变成了下标的排序，将s1下标45132排序得到s2下标12345。因为
不能有extra space,可以用quick sort, 或者heap sort，都是O(nlgn)。 | g*****u
发帖数: 298 | 4 想法很好，可是在s1中找s2对应元素的位置cost是多少？
s2[
=
【在 c*****o 的大作中提到】
: 可不可以这样考虑呢，s2 = 12435, s2[1] = 1,s2[2] = 2,s2[3] = 4, s[4] = 3, s2[
: 5] = 5.在s1= 45312找到相对元素位置, s1[4] = 1, s1[5]= 2, s1[1] = 4, s1[3] =
: 3, s1[2] = 5. 问题就变成了下标的排序，将s1下标45132排序得到s2下标12345。因为
: 不能有extra space,可以用quick sort, 或者heap sort，都是O(nlgn)。
| w****i
发帖数: 964 | 5 O(n)
【在 g*****u 的大作中提到】
: 想法很好，可是在s1中找s2对应元素的位置cost是多少？
:
: s2[
: =
| g*****u
发帖数: 298 | 6 能否说的详细些？
比如S1=45231, S2=14532
对于S1中每个元素找到其在S2中的位置，不能用extra mem
O(n)怎么做？
【在 w****i 的大作中提到】
: O(n)
| d**a
发帖数: 84 | 7 我觉得可以这么搞：
1. 排序S1，变成1234....N, O(N*logN)
2. 1234...N => S2, O(N)
这个可以利用任意一个(12...N)的permutation是由几个环组成来完成。
这个过程需要修改S2来记录那个环已经被处理过。
不知道有没有不需要修改s2的方法。 | d**a
发帖数: 84 | 8 这个无法实现吧，如果s2是123....N那岂不排序就O(N)了。
【在 w****i 的大作中提到】
: O(n)
| g*****u
发帖数: 298 | 9 第二步能否写个伪代码？
你不是还是得知道1，2，3...在S2中的位置么。
我理解的有问题？
【在 d**a 的大作中提到】
: 我觉得可以这么搞：
: 1. 排序S1，变成1234....N, O(N*logN)
: 2. 1234...N => S2, O(N)
: 这个可以利用任意一个(12...N)的permutation是由几个环组成来完成。
: 这个过程需要修改S2来记录那个环已经被处理过。
: 不知道有没有不需要修改s2的方法。
| d**a
发帖数: 84 | 10 s2=9 2 7 3 1 6 8 4 5
4 rings:
951
2
7843
6
use S2 to guide exchanges in s1:
s1[1]=s1[9], s1[5]=s1[9], s1[9]=s[1]
and so on...
【在 g*****u 的大作中提到】
: 第二步能否写个伪代码？
: 你不是还是得知道1，2，3...在S2中的位置么。
: 我理解的有问题？
| g*****u
发帖数: 298 | 11 这4个环怎么得来的？有什么链接讲这个的么？
谢了。
【在 d**a 的大作中提到】
: s2=9 2 7 3 1 6 8 4 5
: 4 rings:
: 951
: 2
: 7843
: 6
: use S2 to guide exchanges in s1:
: s1[1]=s1[9], s1[5]=s1[9], s1[9]=s[1]
: and so on...
| d**a
发帖数: 84 | 12 这个叫permutation group.
wikipedia上有
【在 g*****u 的大作中提到】
: 这4个环怎么得来的？有什么链接讲这个的么？
: 谢了。
|
|
