输入 , 如何在O(n)的时间,用O(1)的空间,将这个序列顺序改为 。
输入:1234567dbcdefg
则输出1a2b3c4d5e6f7g
公式:y = 2x mod (2n -1),
顾而 x = (y + k * (2n - 1))/2
这里k可以化成y相关,因为i 范围为0--2n-1所以y+k(2n-1) 必须在0 --(2n-1)*2
所以y 与k*(2n-1)同奇同偶。故 k= y%2;
因此有:x=(y + (y%2)*(2n - 1))/2;
别人的代码:
/*=============================================*\
完美洗牌算法:
有个长度为2n的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn},
希望排序后{a1,b1,a2,b2,....,an,bn},
要求时间复杂度o(n),空间复杂度0(1)。
\*=============================================*/
#include <iostream>
#include <string>
using namespace std;
int main(){
string arr("1234567abcdefg");
int index = arr.length() / 2;
int temp = arr[index];
while(index != 1){
int tempIndex = (index + (index % 2) * (arr.length() - 1)) / 2;
arr[index] = arr[tempIndex];
index = tempIndex;
}
arr[1] = temp;
cout << arr << endl;
system("pause");
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)