July_algorithm 3.数组.pdf

《July_algorithm 3.数组.pdf》由会员分享，可在线阅读，更多相关《July_algorithm 3.数组.pdf（80页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数组七月算法邹博2015年10月24日10月算法在线班2/求局部最大值 给定一个无重复元素的数组A0N-1，求找到一个该数组的局部最大值。规定：在数组边界外的值无穷小。即：A0A-1，AN-1 AN。显然，遍历一遍可以找到全局最大值，而全局最大值显然是局部最大值。可否有更快的办法？10月算法在线班3/问题分析 定义：若子数组Arrayfrom,to满足 ArrayfromArrayfrom-1 ArraytoArrayto+1 称该子数组为“高原数组”。若高原数组长度为1，则该高原数组的元素为局部最大值。10月算法在线班4/算法描述 使用索引left、right分别指向数组首尾，根据定义，该数

2、组为高原数组。求中点mid=(left+right)/2 AmidAmid+1，子数组Aleftmid为高原数组丢弃后半段：right=mid Amid+1Amid，子数组Amidright高原数组丢弃前半段：left=mid+1 递归直至left=right时间复杂度为O(logN)。10月算法在线班5/Code10月算法在线班6/第一个缺失的整数 给定一个数组A0N-1，找到从1开始，第一个不在数组中的正整数。如3,5,1,2,-3,7,14,8输出4。10月算法在线班7/循环不变式 思路：将找到的元素放到正确的位置上，如果最终发现某个元素一直没有找到，则该元素即为所求。循环不变式：如果某

3、命题初始为真，且每次更改后仍然保持该命题为真，则若干次更改后该命题仍然为真。为表述方便，下面的算法描述从1开始数。10月算法在线班8/利用循环不变式设计算法 假定前i-1个数已经找到，并且依次存放在A1,2,i-1中，继续考察Ai：若Aii且Ai1，则Ai在A1,2,i-1中已经出现过，可以直接丢弃。若Ai为负，则更应该丢弃它。若Aii且AiN，则Ai应该位于后面的位置上，则将AAi和Ai交换。若AiN，由于缺失数据一定小于N，则Ai丢弃。若Aii，则Ai位于正确的位置上，则i加1，循环不变式扩大，继续比较后面的元素。10月算法在线班9/合并相同的分支 整理算法描述：若Aii或者AiN，则丢弃

4、Ai 若Aii，则将AAi和Ai交换。若Aii，i加1，继续比较后面的元素。思考：如何快速丢弃Ai？将AN赋值给Ai，然后N减1。10月算法在线班10/Code10月算法在线班11/查找旋转数组的最小值 假定一个排序数组以某个未知元素为支点做了旋转，如：原数组0 1 2 4 5 6 7旋转后得到4 5 6 7 0 1 2。请找出旋转后数组的最小值。假定数组中没有重复数字。10月算法在线班12/分析 旋转之后的数组实际上可以划分成两个有序的子数组：前面子数组的大小都大于后面子数组中的元素；4 5 6 7 0 1 2 注意到实际上最小的元素就是两个子数组的分界线。10月算法在线班13/寻找循环数组

5、最小值：4 5 6 7 0 1 2 用索引left，right分别指向首尾元素，元素不重复。若子数组是普通升序数组，则AleftAright 计算中间位置mid=(low+high)/2;显然，Alowmid与Amid+1high必有一个是循环升序数组，一个是普通升序数组。若：AmidAhigh，说明子数组Amid+1,mid+2,high循环升序；更新low=mid+1；若：AmidAhigh，说明子数组Amid+1,mid+2,high普通升序；更新：high=mid10月算法在线班14/代码10月算法在线班15/零子数组 求对于长度为N的数组A，求连续子数组的和最接近0的值。如：数组A、

6、1,-2,3,10,-4,7,2,-5 它是所有子数组中，和最接近0的是哪个？10月算法在线班16/算法流程 申请比A长1的空间sum-1,0,N-1，sumi是A的前i项和。trick：定义sum-1=0 显然有：算法思路：对sum-1,0,N-1排序，然后计算sum相邻元素的差的绝对值，最小值即为所求 在A中任意取两个前缀子数组的和求差的最小值 1isumjsumAjikk10月算法在线班17/零子数组的讨论 计算前n项和数组sum和计算sum相邻元素差的时间复杂度，都是O(N)，排序的时间复杂度认为是O(NlogN)，因此，总时间复杂度：O(NlogN)。思考：如果需要返回绝对值最小的子

7、数组本身呢？10月算法在线班18/Code10月算法在线班19/最大子数组和 给定一个数组A0,n-1，求A的连续子数组，使得该子数组的和最大。例如 数组：1,-2,3,10,-4,7,2,-5，最大子数组：3,10,-4,7,210月算法在线班20/分析定义：前缀和sumi=a0+a1+.+ai则：ai,j=sumj-sumi-1(定义p-1=0)算法过程1.求i前缀sumi：遍历i：0in-1sumi=sumi-1+ai2.计算以ai结尾的子数组的最大值对于某个i：遍历0ji，求sumj的最小值msumi-m即为以ai结尾的数组中最大的子数组的值3.统计sumi-m的最大值，0in-11、

8、2、3步都是线性的，因此，时间复杂度O(n)。1isumjsumajikk10月算法在线班21/进一步的分析 记Si为以Ai结尾的数组中和最大的子数组 则：Si+1=max(Si+Ai+1,Ai+1)S0=A0 遍历i：0i n-1 动态规划：最优子问题 时间复杂度：O(n)10月算法在线班22/动态规划Code10月算法在线班23/思考 若除了输出最大子数组的和，还需要输出最大子数组本身，应该怎么做？10月算法在线班24/参考代码10月算法在线班25/最大间隔 给定整数数组A0N-1，求这N个数排序后最大间隔。如：1,7,14,9,4,13的最大间隔为4。排序后：1,4,7,9,13,14，

9、最大间隔是13-9=4 显然，对原数组排序，然后求后项减前项的最大值，即为解。可否有更好的方法？10月算法在线班26/问题分析 假定N个数的最大最小值为max，min，则这N个数形成N-1个间隔，其最小值是 如果N个数完全均匀分布，则间距全部是且最小；如果N个数不是均匀分布，间距不均衡，则最大间距必然大于1Nminmax1Nminmax1Nminmax10月算法在线班27/解决思路 思路：将N个数用间距分成N-1个区间，则落在同一区间内的数不可能有最大间距。统计后一区间的最小值与前一区间的最大值的差即可。若没有任何数落在某区间，则该区间无效，不参与统计。显然，这是借鉴桶排序/Hash映射的思想

10、。1Nminmax10月算法在线班28/桶的数目 同时，N-1个桶是理论值，会造成若干个桶的数目比其他桶大1，从而造成统计误差。如：7个数，假设最值为10、80，如果适用6个桶，则桶的大小为70/6=11.66，每个桶分别为：10,21、22,33、34,44、45,56、57,68、69,80，存在大小为12的桶，比理论下界11.66大。因此，使用N个桶。10月算法在线班29/Code10月算法在线班30/字符串的全排列 给定字符串S0N-1，设计算法，枚举S的全排列。10月算法在线班31/递归算法 以字符串1234为例：1 234 2 134 3 214 4 231 如何保证不遗漏 保证递

11、归前1234的顺序不变10月算法在线班32/递归Code10月算法在线班33/如果字符有重复 去除重复字符的递归算法 以字符1223为例：1 223 2 123 3 221 带重复字符的全排列就是每个字符分别与它后面非重复出现的字符交换。即：第i个字符与第j个字符交换时，要求i,j)中没有与第j个字符相等的数。10月算法在线班34/Code10月算法在线班35/重复字符的全排列递归算法时间复杂度 f(n)=n*f(n-1)+n2 f(n-1)=(n-1)*f(n-2)+(n-1)2 f(n)=n*(n-1)*f(n-2)+(n-1)2)+n2 f(n-2)=(n-2)*f(n-3)+(n-2)

12、2 f(n)=n*(n-1)*(n-2)*f(n-3)+(n-2)2)+n*(n-1)2+n2=n*(n-1)*(n-2)*f(n-3)+n*(n-1)*(n-2)2+n*(n-1)2+n2=.n+110月算法在线班36/空间换时间10月算法在线班37/空间换时间的方法 如果是单字符，可以使用mark256；如果是整数，可以遍历整数得到最大值max和最小值min，使用markmax-min+1；如果是浮点数或其他结构，考虑使用Hash。事实上，如果发现整数间变化太大，也应该考虑使用Hash；可以认为整数/字符的情况是最朴素的Hash。10月算法在线班38/全排列的非递归算法 起点：字典序最小的

13、排列，例如12345 终点：字典序最大的排列，例如54321 过程：从当前排列生成字典序刚好比它大的下一个排列 如：21543的下一个排列是23145 如何计算？10月算法在线班39/21543的下一个排列的思考过程 逐位考察哪个能增大 一个数右面有比它大的数存在，它就能增大 那么最后一个能增大的数是x=1 1应该增大到多少？增大到它右面比它大的最小的数y=3 应该变为23xxx 显然，xxx应由小到大排：145 得到2314510月算法在线班40/全排列的非递归算法：整理成算法语言 步骤：后找、小大、交换、翻转 后找：字符串中最后一个升序的位置i，即：SkSk+1(ki)，Si=sum：xi

14、可以为0；注意，这里是“可以”可以能够：可能。10月算法在线班47/分支限界法10月算法在线班48/数理逻辑的重要应用：分支限界的条件 分支限界的条件是充分条件吗？在新题目中，如何发现分支限界的条件。学会该方法，比此问题本身更重要10月算法在线班49/考虑负数的情况 枚举法肯定能得到正确的解 如何对负数进行分支限界？可对整个数组A0N-1正负排序，使得负数都在前面，正数都在后面，使用剩余正数的和作为分支限界的约束：如果Ai为负数：如果全部正数都算上还不够，就不能选Ai；如果递归进入了正数范围，按照数组是全正数的情况正常处理；10月算法在线班50/带负数的分支限界10月算法在线班51/求字符串的

15、最长回文子串 回文子串的定义：给定字符串str，若s同时满足以下条件：s是str的子串 s是回文串 则，s是str的回文子串。该算法的要求，是求str中最长的那个回文子串。10月算法在线班52/解法1 枚举中心位置int LongestPalindrome(const char*s,int n)int i,j,max;if(s=0|n 1)return 0;max=0;for(i=0;i=0)&(i+j max)max=j*2+1;for(j=0;(i-j=0)&(i+j+1 max)max=j*2+2;return max;10月算法在线班53/算法解析 step1预处理 因为回文串有奇数和

16、偶数的不同。判断一个串是否是回文串，往往要分开编写，造成代码的拖沓。一个简单的事实：长度为n的字符串，共有n-1个“邻接”，加上首字符的前面，和末字符的后面，共n+1的“空”(gap)。因此，字符串本身和gap一起，共有2n+1个，必定是奇数；abbc#a#b#b#c#aba#a#b#a#因此，将待计算母串扩展成gap串，计算回文子串的过程中，只考虑奇数匹配即可。10月算法在线班54/数组int Psize 字符串12212321 S=$#1#2#2#1#2#3#2#1#;trick：为处理统一，最前面加一位未出现的字符，如$用一个数组Pi来记录以字符Si为中心的最长回文子串向左/右扩张的长度

17、(包括Si)，比如S和P的对应关系：S#1#2#2#1#2#3#2#1#P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1Pi-1正好是原字符串中回文串的总长度 若Pi为偶数，考察x=Pi/2、2*x-1 思考：若Pi为奇数呢？答：不考虑！(为何？)10月算法在线班55/分析算法核心我们的任务：假定已经得到了前i个值，考察i+1如何计算即：在P0.i-1已知的前提下，计算Pi的值。换句话说，算法的核心，是在P0.i-1已知的前提下，能否给Pi的计算提供一点有用的信息呢？1、通过简单的遍历，得到i个三元组k,Pk,k+Pk，0ki-1trick：以k为中心的字符形成的最大回文

18、子串的最右位置是k+Pk-12、以k+Pk为关键字，挑选出这i个三元组中，k+Pk最大的那个三元组，不妨记做(id,Pid，Pid+id)。进一步，为了简化，记mx=Pid+id，因此，得到三元组为(id,Pid,mx)，这个三元组的含义非常明显：所有i个三元组中，向右到达最远的位置，就是mx；3、在计算Pi的时候，考察i是否落在了区间0,mx)中；若i在mx的右侧，说明0,mx)没有能够控制住i，P0.i-1的已知，无法给Pi的计算带来有价值信息；若i在mx的左侧，说明0,mx)控制(也有可能部分控制)了i，现在以图示来详细考察这种情况。10月算法在线班56/Manacher递推关系 记i关

19、于id的对称点为j(=2*id-i)，若此时满足条件mx-iPj：记my为mx关于id的对称点(my=2*id-mx)；由于以Sid为中心的最大回文子串为Smy+1idmx-1，即：Smy+1,id与Sid,mx-1对称，而i和j关于id对称，因此Pi=Pj(Pj是已知的)。10月算法在线班57/Manacher递推关系 记i关于id的对称点为j(=2*id-i)，若此时满足条件mx-iPj：记my为mx关于id的对称点(my=2*id-mx)；由于以Sid为中心的最大回文子串为Smy+1idmx-1，即：Smy+1,id与Sid,mx-1对称，而i和j关于id对称，因此Pi至少等于mx-i(

20、图中绿色框部分)。10月算法在线班58/Manacher Code10月算法在线班59/原始算法的个人改进意见 Pj mx i：Pi=mx i Pj 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个元素a3的位置，即6-3；第7个元素b3到了原第5个元素b1的位置，即7-5；第8个元素b4到了原第7个元素b3的位置，即8-7；后n个元素，

21、第i个元素的最终位置为：(2*(i-n)-1=2*i-2*n-1=(2*i)%(2*n+1)10月算法在线班69/两个圈 我们得到两个圈 1 2 4 8 7 5 1 3 6 310月算法在线班70/K个圈 对于2*n=(3k-1)这种长度的数组，恰好只有k个圈，且每个圈的起始位置分别是1,3,9，.3(k-1)10月算法在线班71/若：2m可以写成3k-1的形式10月算法在线班72/任意长度数组的完美洗牌算法10月算法在线班73/循环移位(AB)=BA10月算法在线班74/完美洗牌算法流程 输入数组A1.2*n step 1 找到 2*m=3k-1，且3k2*n3(k+1)step 2 把am

22、+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继续使用本算法。10月算法在线班75/完美洗牌代码10月算法在线班76/依据 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)=610月算法在线班77/附：算法原文10月算法在线班78/进一步的思考要求输出是a1,b1,a2,b2an,bn，而完美洗牌算法输出是b1,a1,b2

23、,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,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的原根10月算法在线班79/我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班80/感谢大家恳请大家批评指正！