[经典面试题]完美洗牌算法 傷城~ 2022-02-01 19:15 268阅读 0赞 **题目** 有个长度为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) **代码一** /*--------------------------------------------- * 日期:2015-02-13 * 作者:SJF0115 * 题目: 完美洗牌算法 * 来源:2013年UC的校招笔试题 * 博客: -----------------------------------------------*/ #include <iostream> using namespace std; class Solution { public: void PerfectShuffle(int *A,int n){ if(n <= 1){ return; }//if // 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; }//for }//for } }; 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]<<" "; }//for 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)。仍然但不到题目要求。 **代码二** /*--------------------------------------------- * 日期:2015-02-13 * 作者:SJF0115 * 题目: 完美洗牌算法 * 来源:2013年UC的校招笔试题 * 博客: -----------------------------------------------*/ #include <iostream> using namespace std; class Solution { public: void PerfectShuffle(int *A,int n){ if(n <= 1){ return; }//if // 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]); }//for --left; ++right; }//for } }; 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]<<" "; }//for 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)对原始位置的变化做如下分析: ![这里写图片描述][20150213112150426] (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]; // 2 * i % (2 * n + 1) int mod = 2 * n + 1; // 实际位置 int next = start * 2 % mod; // 按环移动位置 while(next != start){ swap(pre,a[next]); next = 2 * next % mod; }//while 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)需要交换一部分数组元素 ![这里写图片描述][20150213131803002] (下面使用\[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 ![这里写图片描述][20150213140249105] ![这里写图片描述][20150213140306905] **循环左移** 介绍一下时间复杂度为O(n),空间复杂度为O(1)的循环移位操作。 思路: 假设循环左移m位。把数组分成两段,第一段为前m个元素,第二段为剩余元素。把第一段和第二段先各自翻转一下,再将整体翻转下。 // 翻转 start 开始位置 end 结束位置 void Reverse(int *a,int start,int end){ while(start < end){ swap(a[start],a[end]); ++start; --end; }//while } // 循环左移m位 n数组长度 下标从1开始 void LeftRotate(int *a,int m,int n){ // 翻转前m位 Reverse(a,1,m); // 翻转剩余元素 Reverse(a,m+1,n); // 整体翻转 Reverse(a,1,n); } 代码: /*--------------------------------------------- * 日期:2015-02-13 * 作者:SJF0115 * 题目: 完美洗牌算法 * 来源:2013年UC的校招笔试题 * 博客: -----------------------------------------------*/ #include <iostream> using namespace std; class Solution { public: // 完美洗牌算法 void PerfectShuffle(int *a,int n){ while(n >= 1){ // 计算环的个数 int k = 0; // 3^1 int r = 3; // 2 * m = 3^k - 1 // m <= n -> 2 * m <= 2 * n -> 3^k - 1 <= 2 * n // 寻找最大的k使得3^k - 1 <= 2*n while(r - 1 <= 2*n){ r *= 3; ++k; }//while int m = (r / 3 - 1) / 2; // 循环左移n-m位 LeftRotate(a+m,n-m,n); // k个环 环起始位置start: 1,3...3^(k-1) for(int i = 0,start = 1;i < k;++i,start *= 3) { // 走圈 CycleLeader(a,start,m); }//for a += 2*m; n -= m; } } private: // 翻转 start 开始位置 end 结束位置 void Reverse(int *a,int start,int end){ while(start < end){ swap(a[start],a[end]); ++start; --end; }//while } // 循环右移m位 n数组长度 下标从1开始 void LeftRotate(int *a,int m,int n){ // 翻转前m位 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]; // 2 * i % (2 * n + 1) int mod = 2 * n + 1; // 实际位置 int next = start * 2 % mod; // 按环移动位置 while(next != start){ swap(pre,a[next]); next = 2 * next % mod; }//while 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]<<" "; }//for cout<<endl; } **拓展一** **问题:**如果输入是a1,a2,……an, b1,b2,……bn, c1,c2,……cn,要求输出是c1,b1,a1,c2,b2,a2,……cn,bn,an怎么办? **分析:** 这个问题本质上其实还是上面的完美洗牌算法一样,我们一样还是分析其规律。 ![这里写图片描述][20150214103810904] 对于原数组位置i的元素,新位置是**(3\*i)%(3n+1)** ![这里写图片描述][20150214104119012] ![这里写图片描述][20150214104148399] 图中所说的步骤三四五和上面的三四五大体一样,只是细节不太一样,看图就明白了。 引用: [http://blog.csdn.net/v\_july\_v/article/details/10212493][http_blog.csdn.net_v_july_v_article_details_10212493] [http://ask.julyedu.com/question/33][http_ask.julyedu.com_question_33] [http://blog.csdn.net/caopengcs/article/details/10521603][http_blog.csdn.net_caopengcs_article_details_10521603] [http://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400\#400][http_cs.stackexchange.com_questions_332_in-place-algorithm-for-interleaving-an-array_400_400] [20150213112150426]: /images/20220126/4141d805c72e452a81d5886696c17867.png [20150213131803002]: /images/20220126/927b08cd7e994be4ac8fe2b6f63c3765.png [20150213140249105]: /images/20220126/ca70bd6a7c4448da83f0196c771c8623.png [20150213140306905]: /images/20220126/b248aef6b9f64d888576db49175d3c93.png [20150214103810904]: /images/20220126/f8cc3363b7934fe9a4b9b29d62084850.png [20150214104119012]: /images/20220126/63c85106f48948e79e1e6e522d6841e9.png [20150214104148399]: /images/20220126/6d487f727e1b44d98a3fcf2101efaa74.png [http_blog.csdn.net_v_july_v_article_details_10212493]: http://blog.csdn.net/v_july_v/article/details/10212493 [http_ask.julyedu.com_question_33]: http://ask.julyedu.com/question/33 [http_blog.csdn.net_caopengcs_article_details_10521603]: http://blog.csdn.net/caopengcs/article/details/10521603 [http_cs.stackexchange.com_questions_332_in-place-algorithm-for-interleaving-an-array_400_400]: http://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400#400
还没有评论,来说两句吧...