算法学习 3.数组.pdf

《算法学习 3.数组.pdf》由会员分享，可在线阅读，更多相关《算法学习 3.数组.pdf（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数组七月算法邹博2015年4月14日4月算法在线班2/数组 仅指存储方式为数组，非考察语言级数组的问题 有些题目非常难，甚至是NP难解的 后面将有NP的实例 往往有很难的面试压轴大题 完美洗牌算法 本次目标：除了学会算法本身，在这个过程中，探讨算法如何设计？理清从特殊到一般的分析思路。4月算法在线班3/寻找和为定值的两个数 输入一个数组A0N-1和一个数字Sum，在数组中查找两个数Ai,Aj，使得Ai+Aj=Sum。4月算法在线班4/暴力求解 从数组中任意选取两个数x,y，判定它们的和是否为输入的数字M。时间复杂度为O(N2)，空间复杂度O(1)。4月算法在线班5/稍好一点的方法 如果数组是无

2、序的，先排序(NlogN)，然后用两个指针i，j，各自指向数组的首尾两端，令i=0，j=n-1，然后i+，j-，逐次判断ai+aj是否等于Sum：如果ai+ajsum，则i不变，j-；如果ai+aj=sum：xi可以为0；4月算法在线班12/分支限界法4月算法在线班13/数理逻辑的重要应用：分支限界的条件 分支限界的条件是充分条件吗？在新题目中，如何发现分支限界的条件。学会该方法，比此问题本身更重要4月算法在线班14/考虑负数的情况 枚举法肯定能得到正确的解 如何对负数进行分支限界？可对整个数组A0N-1正负排序，使得负数都在前面，正数都在后面，使用剩余正数的和作为分支限界的约束：如果Ai为负

3、数：如果全部正数都算上还不够，就不能选Ai；如果递归进入了正数范围，按照数组是全正数的情况正常处理；注：正负排序马上要讲到4月算法在线班15/带负数的分支限界4月算法在线班16/荷兰国旗问题 现有红、白、蓝三个不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。4月算法在线班17/问题分析 问题转换为：给定数组A0N-1，元素只能取0、1、2三个值，设计算法，使得数组排列成“000011112222”的形式。借鉴快速排序中partition的过程。定义三个指针：b

4、egin=0、current=0、end=N-1：Acur=2，则Acur 与Aend交换，end-，cur不变 Acur=1，则cur+，begin不变，end不变 Acur=0，则：若begin=cur，则begin+，cur+若begincur，则Acur与Abegin交换，begin+，cur不变4月算法在线班18/Code1 Acur=2，则Acur 与Aend交换，end-，cur不变 Acur=1，则cur+，begin不变，end不变 Acur=0，则：若begin=cur，则begin+，cur+若begincur，则Acur与Abegin交换，begin+，cur不变4月算

5、法在线班19/进一步的考虑：略做优化 current扫过的位置，即：begin,cur)区间内，一定没有2在前面的Acur=2中，已经被替换到数组后面了 因此：Abegin要么是0，要么是1，不可能是2 考察begin指向的元素的值：若begincur，则必有Abegin=1 用归纳法，使用begin/cur/end的演示过程证明上述结论 因此，当Acur=0时，若begincur，因为Abegin=1，则交换后，Acur=1，此时，可以cur+；4月算法在线班20/优化后的图示演示4月算法在线班21/Code2 Acur=2，则Acur 与Aend交换，end-，cur不变 Acur=1，则

6、cur+，begin不变，end不变 Acur=0，则：若begin=cur，则begin+，cur+若begincur，则Acur与Abegin交换，begin+，cur+4月算法在线班22/Code24月算法在线班23/荷兰国旗问题带来的思考 在begin/cur/end的循环中，cur遇到0和遇到2，begin和end的处理方式不对称 遇到0：begin+,cur+遇到2：end-，cur不变 若初值给定如下：begin=0、current=N-1、end=N-1，如何完成代码？4月算法在线班24/Code34月算法在线班25/“乌克兰国旗”问题 如果是分成两部分呢？给定整数数组，要求奇

7、数在前，偶数在后 奇偶排序 给定实数数组，要求负数在前，正数在后 正负排序4月算法在线班26/讨论：荷兰国旗问题的其他方案 荷兰国旗中，0，1，2分别计数，然后根据三个计数值，赋值数组；是否可行 将（0,1）（2）根据快速排序的Patition，分成两堆（不妨使用1.5或者其他数作为PivotKey），然后，将（0）（1）根据快速排序的Patition，分成两堆（不妨使用0.5或者其他数作为PivotKey）。4月算法在线班27/完美洗牌算法 长度为2n的数组a1,a2,a3,.,an,b1,b2,b3,.,bn，经过整理后变成a1,b1,a2,b2,.,an,bn，要求时间复杂度O(n)，空

8、间复杂度O(1)。4月算法在线班28/步步前移观察变换前后两个序列的特点，我们可做如下一系列操作：第步确定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，b4b4已在最后的位置，不需要再交换。如此，经过上述3个步骤后，得到我们最后想要的序列。移动n-1次，第i次将n-i个元素后移。时间复杂度为O（N2）。4月算法在线班29/中间交换 每次让序列中最中间的元素进行交换

9、。对于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，b44月算法在线班30/中间交换4月算法在线班31/中间交换4月算法在线班32/玩乐中带来的算法思维4月算法在线班33/完美洗牌算法 2004年，microsoft的Peiyush Jain在他发表一篇名为：“A Simple In-Place Algorithm for In-Shuf

10、fle”的论文中提出了完美洗牌算法。4月算法在线班34/位置变换a1,a2,a3,.an,b1,b2,b3.bn b1,a1,b2,a2,b3,a3.bn,an设定数组的下标范围是1.2n。考察元素的最终位置：以n=4为例，前n个元素中，第1个元素a1到了原第2个元素a2的位置，即1-2；第2个元素a2到了原第4个元素a4的位置，即2-4；第3个元素a3到了原第6个元素b2的位置，即3-6；第4个元素a4到了原第8个元素b4的位置，即4-8；前n个元素中，第i个元素的最终位置为（2*i）。后n个元素，可以看出：第5个元素b1到了原第1个元素a1的位置，即5-1；第6个元素b2到了原第3个元素a

11、3的位置，即6-3；第7个元素b3到了原第5个元素b1的位置，即7-5；第8个元素b4到了原第7个元素b3的位置，即8-7；后n个元素，第i个元素的最终位置为：(2*(i-n)-1=2*i-2*n-1=(2*i)%(2*n+1)4月算法在线班35/两个圈 我们得到两个圈 1 2 4 8 7 5 1 3 6 34月算法在线班36/K个圈 对于2*n=（3k-1）这种长度的数组，恰好只有k个圈，且每个圈的起始位置分别是1,3,9，.3(k-1)4月算法在线班37/若：2m可以写成3k-1的形式4月算法在线班38/任意长度数组的完美洗牌算法4月算法在线班39/循环移位(AB)=BA4月算法在线班40

12、/完美洗牌算法流程 输入数组A1.2*n step 1 找到 2*m=3k-1，且3k2*n3(k+1)step 2 把am+1m+n那部分循环右移m位 step 3 对每个i=0,1,2.k-1，3i是每个圈的起始位置，做cycle_leader算法；注：因为子数组长度为m，所以对2*m+1取模 step 4 对数组的剩余部分A2*m+1.2*n继续使用本算法。4月算法在线班41/完美洗牌代码4月算法在线班42/依据 2是3的原根，2是9的原根 20,21=1,2 20,21,22,23,24,25,26,27,28mod 9=1,2,4,8,7,5 而(9)=64月算法在线班43/附：算法

13、原文4月算法在线班44/进一步的思考要求输出是a1,b1,a2,b2an,bn，而完美洗牌算法输出是b1,a1,b2,a2,bn,an,怎么办？先把a部分和b部分交换，或者最后再交换相邻的两个位置不够美观。原数组第一个和最后一个不变，中间的2*(n-1)项用原始的完美洗牌算法。逆完美洗牌问题：给定b1,a1,b2,a2,bn,an，要求输出a1,a2,a3,an,b1,b2,b3,bn。既然完美洗牌问题可以通过若干圈来解决，那么，逆完美洗牌问题仍然存在是若干圈，并且2*n=（3k-1）这种长度的数组恰好只有k个圈的结论仍然成立。完美洗多付牌：给定a1,a2,an,b1,b2,bn,c1,c2,

14、cn，要求输出是c1,b1,a1,c2,b2,a2,cn,bn,an2付牌的结论：2是群(Z/3k)*最小生成元，且(3k-1)这种长度的数组，恰好只有k个圈考察是否存在某数字p（如5、7、11、13等），使得数字3是群(Z/pk)*的最小生成元，再验证p是否存在结论(pk-1)这种长度的数组，恰好只有k个圈。提示：3是7的原根，是49的原根，于是3是7k的原根4月算法在线班45/参考文献http:/ Jain,A Simple In-Place Algorithm for In-Shuffle,Microsoft,July,2004(完美洗牌)https:/ 更多算法面试题在官网 http:/ 直播课程 问答社区 contact us：微博 七月问答 七月算法4月算法在线班47/感谢大家恳请大家批评指正！