r*****e
发帖数: 146 | 1 Given two array, array1: a1,a2,a3....,an, Array 2: b1,b2,b3...bn. How to
merge them in the form of a1,b1,a2,b2,....an,bn in O(n) time complexity and
O(1) space? |
h*******e
发帖数: 1377 | |
r*****e
发帖数: 146 | 3 能给个链接么？google了一下，实在找不到啊。。
【在 h*******e 的大作中提到】
: 以前冷爵讨论过吧用分治法。
|
c**s
发帖数: 159 | 4 时间复杂度为O(n)的in-place算法 可以搜perfect shuffle problem 很复杂。
还有个O(nlogn)的分治in-place算法 用到循环移位 可以比较简单的解决：
（1） 把b部分循环移 n/2 位 这样 中间的n个元素元素是a的后n/2个和b的后n/2
（2） 对中间n个元素递归完成任务 这样 中间n个满足要求了
(3) 对全体的后3/4×（2n) 的元素 循环移动 n/2位， 这样后面n个元素满足要求
前面n个元素又是一半的子问题
（4）完成前一半的n个的任务
循环移位是O(n)的
复杂度 T(n) = 2 * T(n / 2) + O(n)
总复杂度T(n) = O(nlogn) |
h*******e
发帖数: 1377 | 5 收藏楼上 O(n) 做法了
【在 c**s 的大作中提到】
: 时间复杂度为O(n)的in-place算法 可以搜perfect shuffle problem 很复杂。
: 还有个O(nlogn)的分治in-place算法 用到循环移位 可以比较简单的解决：
: （1） 把b部分循环移 n/2 位 这样 中间的n个元素元素是a的后n/2个和b的后n/2
: （2） 对中间n个元素递归完成任务 这样 中间n个满足要求了
: (3) 对全体的后3/4×（2n) 的元素 循环移动 n/2位， 这样后面n个元素满足要求
: 前面n个元素又是一半的子问题
: （4）完成前一半的n个的任务
: 循环移位是O(n)的
: 复杂度 T(n) = 2 * T(n / 2) + O(n)
: 总复杂度T(n) = O(nlogn)
|
r*****e
发帖数: 146 | 6 谢谢，好好研究一下。。
【在 c**s 的大作中提到】
: 时间复杂度为O(n)的in-place算法 可以搜perfect shuffle problem 很复杂。
: 还有个O(nlogn)的分治in-place算法 用到循环移位 可以比较简单的解决：
: （1） 把b部分循环移 n/2 位 这样 中间的n个元素元素是a的后n/2个和b的后n/2
: （2） 对中间n个元素递归完成任务 这样 中间n个满足要求了
: (3) 对全体的后3/4×（2n) 的元素 循环移动 n/2位， 这样后面n个元素满足要求
: 前面n个元素又是一半的子问题
: （4）完成前一半的n个的任务
: 循环移位是O(n)的
: 复杂度 T(n) = 2 * T(n / 2) + O(n)
: 总复杂度T(n) = O(nlogn)
|
n***i
发帖数: 777 | 7 一个时间 O（n），额外空间 O（1）的很直接的做法。
假定初始: a1 a2 a3 a4 b1 b2 b3 b4
你会发现 a1 和 b4 的位置已经定了，所以你只要关心 | | 之间的内容。
a1 | a2 a3 a4 b1 b2 b3 | b4
如果你交换 a2 和 b1， 然后 交换 a4 和 b3， 你会得到
a1 b1 | a3 b3 a2 b2 | a4 b4， 这时你发现 前面的 a1 b1 和 后面的 a4 b4 都已经
对了
接下去就是再交换。。。
每次交换都让2个新的元素位置正确。
一共交换 n 次，没有额外空间
and
【在 r*****e 的大作中提到】
: Given two array, array1: a1,a2,a3....,an, Array 2: b1,b2,b3...bn. How to
: merge them in the form of a1,b1,a2,b2,....an,bn in O(n) time complexity and
: O(1) space?
|
c**s
发帖数: 159 | 8 问题是程序能算出要交换的下标么。。。
【在 n***i 的大作中提到】
: 一个时间 O（n），额外空间 O（1）的很直接的做法。
: 假定初始: a1 a2 a3 a4 b1 b2 b3 b4
: 你会发现 a1 和 b4 的位置已经定了，所以你只要关心 | | 之间的内容。
: a1 | a2 a3 a4 b1 b2 b3 | b4
: 如果你交换 a2 和 b1， 然后 交换 a4 和 b3， 你会得到
: a1 b1 | a3 b3 a2 b2 | a4 b4， 这时你发现 前面的 a1 b1 和 后面的 a4 b4 都已经
: 对了
: 接下去就是再交换。。。
: 每次交换都让2个新的元素位置正确。
: 一共交换 n 次，没有额外空间
|
n***i
发帖数: 777 | 9 能啊，你把未排好序分为2段，比如
a1 a2 a3 a4 b1 b2 b3 b4 中未排好序的第1半是：a2 a3 a4, 第2半是：b1 b2 b3
你交换的时候，总是把第1半的第1个和第2半的第1个交换，然后第1半的最后一个和第2
半的最后一个交换
你会发现这就是交换的规律
【在 c**s 的大作中提到】
: 问题是程序能算出要交换的下标么。。。
|
d*********g
发帖数: 154 | 10
第2
貌似不对。假设 int[] a = {1, 3, 5, 7, 9}, int[] b = {2, 4, 6, 8, 10}. merge
好之后的结果应该是 1 2 3 4 5 6 7 8 9 10. 按照你的算法：
1. 1 | 3 5 7 9 2 4 6 8 | 10 （3和2交换，9和8交换）
2. 1 2 | 5 7 8 3 4 6 | 9 10 （5和3交换，8和6交换）
3. 1 2 3 | 7 6 5 4 | 8 9 10 （7和5交换，6和4交换）
4. 1 2 3 5 4 7 6 8 9 10 到这里结果就不对了。
Please correct me if I was wrong.
【在 n***i 的大作中提到】
: 能啊，你把未排好序分为2段，比如
: a1 a2 a3 a4 b1 b2 b3 b4 中未排好序的第1半是：a2 a3 a4, 第2半是：b1 b2 b3
: 你交换的时候，总是把第1半的第1个和第2半的第1个交换，然后第1半的最后一个和第2
: 半的最后一个交换
: 你会发现这就是交换的规律
|
|
|
c**s
发帖数: 159 | 11 不对吧。。。。
第2
【在 n***i 的大作中提到】
: 能啊，你把未排好序分为2段，比如
: a1 a2 a3 a4 b1 b2 b3 b4 中未排好序的第1半是：a2 a3 a4, 第2半是：b1 b2 b3
: 你交换的时候，总是把第1半的第1个和第2半的第1个交换，然后第1半的最后一个和第2
: 半的最后一个交换
: 你会发现这就是交换的规律
|
n***i
发帖数: 777 | 12 确实不对，还是用递归，思路跟你的比较像。
n=1
a1 b1
n=2
a1 a2 b1 b2 -> a1 b1 a2 b2
n=4
a1 a2 a3 a4 b1 b2 b3 b3
从中间数左边 n/2 个 和 从中间数右边n/2个交换，得到
a1 a2 b1 b2 a3 a4 b3 b4
然后可以recursively在左边n个和右边n个都成为了n=2的子问题
n=8
a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8 ->
a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 a8 b5 b6 b7 b8 ->
a1 a2 b1 b2 a3 a4 b3 b4 a5 a6 b5 b6 a7 a8 b7 b8 ->
a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8
T(n) = 2T(n/2)+O(n) 所以是 nlgn 算法
但是问题是n 需要是 2^k.如果 n不是2^k， 需要加入padding把它补到2^k然后在结果
中截取需要的部分,所以严格上说空间复杂度说O(1)比较牵强
【在 c**s 的大作中提到】
: 不对吧。。。。
:
: 第2
|
x****j
发帖数: 21 | 13 请问这中间的交换怎么做呀，交换是多少时间度呢？谢谢哈
【在 n***i 的大作中提到】
: 确实不对，还是用递归，思路跟你的比较像。
: n=1
: a1 b1
: n=2
: a1 a2 b1 b2 -> a1 b1 a2 b2
: n=4
: a1 a2 a3 a4 b1 b2 b3 b3
: 从中间数左边 n/2 个 和 从中间数右边n/2个交换，得到
: a1 a2 b1 b2 a3 a4 b3 b4
: 然后可以recursively在左边n个和右边n个都成为了n=2的子问题
|
K**l
发帖数: 2 | 14 2^m次方的时候交换元素的下标很有意思。就是把一个m位的二进制数倒过来。这个貌似
是O(m)的操作。。。
其实在2^m次方的时候如果算cycle的长度就是m，最多者要O(m)次就可以确定cycle是不
是已经走过。所以O(n log n)的算法其实有好多种。纯粹用分治也行。
【在 c**s 的大作中提到】
: 问题是程序能算出要交换的下标么。。。
|
d**********x
发帖数: 4083 | 15 关键字：置换群
【在 K**l 的大作中提到】
: 2^m次方的时候交换元素的下标很有意思。就是把一个m位的二进制数倒过来。这个貌似
: 是O(m)的操作。。。
: 其实在2^m次方的时候如果算cycle的长度就是m，最多者要O(m)次就可以确定cycle是不
: 是已经走过。所以O(n log n)的算法其实有好多种。纯粹用分治也行。
|
K**l
发帖数: 2 | 16 分解成置换cycle的解法有两种极端，2^m次方时cycle长度为m最短。O(n)的解法却是找
到长度最长的时候来解。
【在 d**********x 的大作中提到】
: 关键字：置换群
|
