题目
有个长度为2n的数组{a1,a2,a3,…,an,b1,b2,b3,…,bn},希望排序后{a1,b1,a2,b2,….,an,bn},请考虑有无时间复杂度o(n),空间复杂度0(1)的解法。
来源
2013年UC的校招笔试题
思路一
第①步、确定b1的位置,即让b1跟它前面的a2,a3,a4交换:
a1,b1,a2,a3,a4,b2,b3,b4
第②步、接着确定b2的位置,即让b2跟它前面的a3,a4交换:
a1,b1,a2,b2,a3,a4,b3,b4
第③步、b3跟它前面的a4交换位置:
a1,b1,a2,b2,a3,b3,a4,b4
b4已在最后的位置,不需要再交换。如此,经过上述3个步骤后,得到我们最后想要的序列。但此方法的时间复杂度为O(n^2)
代码一
#include <iostream>
using namespace std;
class Solution {
public:
void PerfectShuffle(int *A,int n){
if(n <= 1){
return;
}
int size = 2*n;
int index,count;
for(int i = n;i < size;++i){
count = n - (i - n) - 1;
index = i;
for(int j = 1;j <= count;++j){
swap(A[index],A[i-j]);
index = i - j;
}
}
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5,6,7,8};
solution.PerfectShuffle(A,4);
for(int i = 0;i < 8;++i){
cout<<A[i]<<" ";
}
cout<<endl;
}
思路二
我们每次让序列中最中间的元素进行两两交换。还是上面的例子:
a1,a2,a3,a4,b1,b2,b3,b4
第①步:交换最中间的两个元素a4,b1:
a1,a2,a3,b1,a4,b2,b3,b4
第②步:最中间的两对元素各自交换:
a1,a2,b1,a3,b2,a4,b3,b4
第③步:交换最中间的三对元素:
a1,b1,a2,b2,a3,b3,a4,b4
此思路同上述思路一样,时间复杂度依然为O(n^2)。仍然但不到题目要求。
代码二
#include <iostream>
using namespace std;
class Solution {
public:
void PerfectShuffle(int *A,int n){
if(n <= 1){
return;
}
int left = n - 1,right = n;
for(int i = 0;i < n-1;++i){
for(int j = left;j < right;j+=2){
swap(A[j],A[j+1]);
}
--left;
++right;
}
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5,6,7,8,9,10};
solution.PerfectShuffle(A,5);
for(int i = 0;i < 10;++i){
cout<<A[i]<<" ";
}
cout<<endl;
}
思路三(完美洗牌算法)
玩过扑克牌的朋友都知道,在一局完了之后洗牌,洗牌人会习惯性的把整副牌大致分为两半,两手各拿一半对着对着交叉洗牌。
2004年,microsoft的Peiyush Jain在他发表一篇名为:“A Simple In-Place Algorithm for In-Shuffle”的论文中提出了完美洗牌算法。
什么是完美洗牌问题呢?即给定一个数组a1,a2,a3,…an,b1,b2,b3..bn,最终把它置换成b1,a1,b2,a2,…bn,an。这个完美洗牌问题本质上与本题完全一致,只要在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可。
(1)对原始位置的变化做如下分析:
(2)依次考察每个位置的变化规律:
a1:1 -> 2
a2:2 -> 4
a3:3 -> 6
a4:4 -> 8
b1:5 -> 1
b2:6 -> 3
b3:7 -> 5
b4:8 -> 7
对于原数组位置i的元素,新位置是(2*i)%(2n+1),注意,这里用2n表示原数组的长度。后面依然使用该表述方式。有了该表达式,困难的不是寻找元素在新数组中的位置,而是为该元素“腾位置”。如果使用暂存的办法,空间复杂度必然要达到O(N),因此,需要换个思路。
(3)我们这么思考:a1从位置1移动到位置2,那么,位置2上的元素a2变化到了哪里呢?继续这个线索,我们得到一个“封闭”的环:
1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1
沿着这个环,可以把a1、a2、a4、b4、b3、b1这6个元素依次移动到最终位置;显然,因为每次只移动一个元素,代码实现时,只使用1个临时空间即可完成。(即:a=t;t=b;b=a)
此外,该变化的另外一个环是:
3 -> 6 -> 3
沿着这个环,可以把a3、b2这2个元素依次移动到最终位置。
void CycleLeader(int *a,int start, int n) {
int pre = a[start];
int mod = 2 * n + 1;
int next = start * 2 % mod;
while(next != start){
swap(pre,a[next]);
next = 2 * next % mod;
}
a[start] = pre;
}
(4)上述过程可以通过若干的“环”的方式完整元素的移动,这是巧合吗?事实上,该问题的研究成果已经由Peiyush Jain在10年前公开发表在A Simple In-Place Algorithm for In-Shuffle, Microsoft, 2004中。原始论文直接使用了一个结论,这里不再证明:对于2*n =(3^k-1)这种长度的数组,恰好只有k个环,且每个环的起始位置分别是1,3,9,…3^(k-1)。
对于上面的例子,长度为8,是3^2-1,因此,只有2个环。环的起始位置分别是1和3。
(5)至此,完美洗牌算法的“主体工程”已经完工,只存在一个“小”问题:如果数组长度不是(3^k-1)呢?
若2n!=(3^k-1),则总可以找到最大的整数m,使得m< n,并且2m=(3^k-1)。
对于长度为2m的数组,调用(3)和(4)中的方法整理元素,剩余的2(n-m)长度,递归调用(5)即可。
(6)需要交换一部分数组元素
(下面使用[a,b]表示从a到b的一段子数组,包括端点)
①图中斜线阴影部分的子数组[1,m]应该和[n + 1,n + m]组成一个数组,调用(3)和(4)中的算法;
②数组[m+1,m+n]循环左移n-m次即可。(循环位移是存在空间复杂度为O(1),时间复杂度为O(n)的算法)
(7)原始问题要输出a1,b1,a2,b2……an,bn,而完美洗牌却输出的是b1,a1,b2,a2,……bn,an。解决办法非常简单:忽略原数组中的a1和bn,对于a2,a3,……an,b1,b2,……bn-1调用完美洗牌算法,即为结论。
举个例子: n = 6
a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,b5,b6
循环左移
介绍一下时间复杂度为O(n),空间复杂度为O(1)的循环移位操作。
思路:
假设循环左移m位。把数组分成两段,第一段为前m个元素,第二段为剩余元素。把第一段和第二段先各自翻转一下,再将整体翻转下。
void Reverse(int *a,int start,int end){
while(start < end){
swap(a[start],a[end]);
++start;
--end;
}
}
void LeftRotate(int *a,int m,int n){
Reverse(a,1,m);
Reverse(a,m+1,n);
Reverse(a,1,n);
}
代码:
#include <iostream>
using namespace std;
class Solution {
public:
void PerfectShuffle(int *a,int n){
while(n >= 1){
int k = 0;
int r = 3;
while(r - 1 <= 2*n){
r *= 3;
++k;
}
int m = (r / 3 - 1) / 2;
LeftRotate(a+m,n-m,n);
for(int i = 0,start = 1;i < k;++i,start *= 3) {
CycleLeader(a,start,m);
}
a += 2*m;
n -= m;
}
}
private:
void Reverse(int *a,int start,int end){
while(start < end){
swap(a[start],a[end]);
++start;
--end;
}
}
void LeftRotate(int *a,int m,int n){
Reverse(a,1,m);
Reverse(a,m+1,n);
Reverse(a,1,n);
}
void CycleLeader(int *a,int start, int n) {
int pre = a[start];
int mod = 2 * n + 1;
int next = start * 2 % mod;
while(next != start){
swap(pre,a[next]);
next = 2 * next % mod;
}
a[start] = pre;
}
};
int main() {
Solution solution;
int A[] = {0,1,2,3,4,5,6,7,8,9,10,11,12};
solution.PerfectShuffle(A,6);
for(int i = 1;i <= 12;++i){
cout<<A[i]<<" ";
}
cout<<endl;
}
拓展一
问题:如果输入是a1,a2,……an, b1,b2,……bn, c1,c2,……cn,要求输出是c1,b1,a1,c2,b2,a2,……cn,bn,an怎么办?
分析: 这个问题本质上其实还是上面的完美洗牌算法一样,我们一样还是分析其规律。
对于原数组位置i的元素,新位置是(3*i)%(3n+1)
图中所说的步骤三四五和上面的三四五大体一样,只是细节不太一样,看图就明白了。
引用:
http://blog.csdn.net/v_july_v/article/details/10212493
http://ask.julyedu.com/question/33
http://blog.csdn.net/caopengcs/article/details/10521603
http://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400#400
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
相关推荐
完美洗牌算法(解决微软面试题的论文)文章中给出了具体的算法思想
有个长度为2n的数组{a1 a2 a3 an b1 b2 b3 bn} 希望排序后{a1 b1 a2 b2 an bn} 请考虑有无时间复杂度o n 空间复杂度0 1 的解法
洗牌算法,整理了常用的洗牌算法,以及优劣比较,复杂度整理和概率等
洗牌算法是我在面试过程中遇到的一个问题,我事后做了整理,与大家分享下思路,这个文档是我自己写的,如要转载,请注明出处。联系方式在文档里有说明。有什么想法或思路希望与我一起交流。
描述了产生随机数算法的思路以及经典的洗牌算法,随机数和洗牌算法也是面试常见的题型
面试经常遇到的,编程算法题。里面包括的都是面试官经常考你的算法设计问题,
斗地主算法类 适合初学者. 可以实现斗地主的洗牌发牌 无JFrame 简单易懂.
JAVA经典算法面试39题及答案,算法是不得不看的
压缩包中三篇论文: 1)完美洗牌问题的出处论文:shuffle.pdf 2)标准反等差映射:yang2013.pdf 3)L=3^N,一种简单的算法:0805.1598v1.pdf
该方案通过BioHashing方法得到用户指纹特征的二进制序列,对得到的序列执行一个改进的洗牌算法进行置乱,最后通过Fuzzy Vault方案将特征值与密钥进行绑定。仿真分析表明,利用Fuzzy Vault方案的容错机制和BCH码的...
算法经典面试题
Java经典面试题-算法.docx
基于折叠技术的大数据样本洗牌算法研究.pdf
经典面试算法题N道,经典面试算法题N道,经典面试算法题N道,经典面试算法题N道
VBS的洗牌算法 算法类资源 可以看看
JAVA经典算法40面试题,包含基本的算法面试代码题。
通过产生随机数进行交换,次数越多,越接近随机
精选 数据结构 算法 微软 谷歌 IT经典 面试题 里面有丰富的编程题目,包含经典的数据结构、算法知识,还有微软谷歌的面试题,这些全是以往收集的,权当大放送。 ps:觉得好要来好评哦。
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
经典算法题经典算法题经典算法题经典算法题经典算法题经典算法题经典算法题经典算法题经典算法题