Google的一个面试题――数组原地置换 - caopengcs的专栏 - 博客频道 - CSDN.NET
给定一个数组a1,a2,a3,...an,b1,b2,b3..bn,最终把它置换成a1,b1,a2,b2,...an,bn。
分析：
本题是完美洗牌问题的变形。
完美洗牌问题： 给定一个数组a1,a2,a3,...an,b1,b2,b3..bn,最终把它置换成b1,a1,b2,a2,...bn,an。
我们先解决完美洗牌问题。
为方便起见，我们考虑的是一个下标从1开始的数组，下标范围是[1..2n]。 我们看一下每个元素最终去了什么地方。
前n个元素 a1 -> a2 a2->a4.... 第i个元素去了 第（2 * i）的位置。
后n个元素a(n + 1)->a1, a(n + 2)->a3... 第i个元素去了第 ((2 * (i - n) ) - 1) = (2 * i - (2 * n + 1)) = (2 * i) % (2 * n + 1) 个位置。
统一一下，任意的第i个元素，我们最终换到了 (2 * i) % (2 * n + 1)的位置，这个取模
Read full article from Google的一个面试题――数组原地置换 - caopengcs的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment