July_algorithm 3.2数组.pdf

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

1、数组七月算法邹博2015年10月24日10月算法在线班2/50天平与假币 有12枚硬币，其中有1枚是假币，但不知道是重还是轻。现给定一架没有砝码的天平，问至少需要多少次称量才能找到这枚假币？进一步：如何证明某个方案是最少次数？10月算法在线班3/50解析 随机将12枚硬币等分成3份，每份4枚；标记为A、B、C三份。将A放于左侧，B放于右侧，用天平称量A和B，分三种情况：1.天平平衡 2.A(左)比B(右)重 3.A(左)比B(右)轻 与2对称，只分析2即可10月算法在线班4/501.天平平衡 天平平衡，说明A、B中都没有假币，假币在C中，将C中的4枚编号为甲乙丙丁。取甲乙用天平称量，若平衡，说

2、明甲乙是真币，丙丁有一枚是假币。取甲丙用天平称量，若不平衡，说明丙是假币；若平衡，说明丙是真币，丁是假币。10月算法在线班5/502.A(左)比B(右)重 说明假币必然在A、B中，C中的4枚都是真币。将A中4枚硬币编号为1234，B中编号为5678，C中编号为甲乙丙丁。选125放于左侧，34甲放于右侧；天平有三种情况：天平平衡：说明678含假币，且假币轻125比34甲重 说明12含假币，且假币重125比34甲轻 说明34含假币，且假币重 或者5是假币，且假币轻 无论如何，最多再一次称量即可找到假币。10月算法在线班6/50理论下界 一次天平称量能得到左倾、右倾、平衡3种情况，则把一次称量当成一

3、位编码，该编码是3进制的。问题转换为：需要多少位编码，能够表示12呢？由于12的轻重未知，有两种可能，因此，需要用3进制表示24。答：假定需要n位，则：3n24 取对数后计算得到n2.89，这表示至少3次才能找到该轻质的假币。10月算法在线班7/50再次思考 题目变成13枚硬币呢？有13枚硬币，其中有1枚是假币，但不知道是重还是轻。现给定一架没有砝码的天平，问至少需要多少次称量才能找到这枚假币？答：3次。10月算法在线班8/50求局部最大值 给定一个无重复元素的数组A0N-1，求找到一个该数组的局部最大值。规定：在数组边界外的值无穷小。即：A0A-1，AN-1 AN。显然，遍历一遍可以找到全局

4、最大值，而全局最大值显然是局部最大值。可否有更快的办法？10月算法在线班9/50问题分析 定义：若子数组Arrayfrom,to满足 ArrayfromArrayfrom-1 ArraytoArrayto+1 称该子数组为“高原数组”。若高原数组长度为1，则该高原数组的元素为局部最大值。10月算法在线班10/50算法描述 使用索引left、right分别指向数组首尾，根据定义，该数组为高原数组。求中点mid=(left+right)/2 AmidAmid+1，子数组Aleftmid为高原数组丢弃后半段：right=mid Amid+1Amid，子数组Amidright高原数组丢弃前半段：lef

5、t=mid+1 递归直至left=right时间复杂度为O(logN)。10月算法在线班11/50Code10月算法在线班12/50第一个缺失的整数 给定一个数组A0N-1，找到从1开始，第一个不在数组中的正整数。如3,5,1,2,-3,7,14,8输出4。10月算法在线班13/50循环不变式 思路：将找到的元素放到正确的位置上，如果最终发现某个元素一直没有找到，则该元素即为所求。循环不变式：如果某命题初始为真，且每次更改后仍然保持该命题为真，则若干次更改后该命题仍然为真。为表述方便，下面的算法描述从1开始数。10月算法在线班14/50利用循环不变式设计算法 假定前i-1个数已经找到，并且依次

6、存放在A1,2,i-1中，继续考察Ai：若Aii且Ai1，则Ai在A1,2,i-1中已经出现过，可以直接丢弃。若Ai为负，则更应该丢弃它。若Aii且AiN，则Ai应该置于后面的位置，即将AAi和Ai交换。若AiN，由于缺失数据N，则Ai丢弃。若AAiAi，则显然不必交换，直接丢弃Ai即可。若Aii，则Ai位于正确的位置上，则i加1，循环不变式扩大，继续比较后面的元素。10月算法在线班15/50合并相同的分支 整理算法描述：若Aii，i加1，继续比较后面的元素。若Aii或AiN或AAiAi，丢弃Ai 若Aii，则将AAi和Ai交换。思考：如何快速丢弃Ai？将AN赋值给Ai，然后N减1。10月算法

7、在线班16/50Code10月算法在线班17/50查找旋转数组的最小值 假定一个排序数组以某个未知元素为支点做了旋转，如：原数组0 1 2 4 5 6 7旋转后得到4 5 6 7 0 1 2。请找出旋转后数组的最小值。假定数组中没有重复数字。10月算法在线班18/50分析 旋转之后的数组实际上可以划分成两个有序的子数组：前面子数组的大小都大于后面子数组中的元素；4 5 6 7 0 1 2 注意到实际上最小的元素就是两个子数组的分界线。10月算法在线班19/50寻找循环数组最小值：4 5 6 7 0 1 2 用索引left，right分别指向首尾元素，元素不重复。若子数组是普通升序数组，则Ale

8、ftAright 计算中间位置mid=(low+high)/2;显然，Alowmid与Amid+1high必有一个是循环升序数组，一个是普通升序数组。若：AmidAhigh，说明子数组Amid+1,mid+2,high循环升序；更新low=mid+1；若：AmidAhigh，说明子数组Amid+1,mid+2,high普通升序；更新：high=mid10月算法在线班20/50代码10月算法在线班21/50零子数组 求对于长度为N的数组A，求连续子数组的和最接近0的值。如：数组A、1,-2,3,10,-4,7,2,-5 它是所有子数组中，和最接近0的是哪个？10月算法在线班22/50算法流程 申

9、请比A长1的空间sum-1,0,N-1，sumi是A的前i项和。trick：定义sum-1=0 显然有：算法思路：对sum-1,0,N-1排序，然后计算sum相邻元素的差的绝对值，最小值即为所求 在A中任意取两个前缀子数组的和求差的最小值 1isumjsumAjikk10月算法在线班23/50零子数组的讨论 计算前n项和数组sum和计算sum相邻元素差的时间复杂度，都是O(N)，排序的时间复杂度认为是O(NlogN)，因此，总时间复杂度：O(NlogN)。思考：如果需要返回绝对值最小的子数组本身呢？10月算法在线班24/50Code10月算法在线班25/50最大子数组和 给定一个数组A0,n-

10、1，求A的连续子数组，使得该子数组的和最大。例如 数组：1,-2,3,10,-4,7,2,-5，最大子数组：3,10,-4,7,210月算法在线班26/50分析 记Si为以Ai结尾的数组中和最大的子数组 则：Si+1=max(Si+Ai+1,Ai+1)S0=A0 遍历i：0i n-1 动态规划：最优子问题 时间复杂度：O(n)10月算法在线班27/50动态规划Code10月算法在线班28/50进一步思考该算法的可行性定义：前缀和sumi=a0+a1+.+ai则：ai,j=sumj-sumi-1(定义p-1=0)算法过程1.求i前缀sumi：遍历i：0in-1sumi=sumi-1+ai2.计算

11、以ai结尾的子数组的最大值对于某个i：遍历0ji，求sumj的最小值msumi-m即为以ai结尾的数组中最大的子数组的值3.统计sumi-m的最大值，0in-11、2、3步都是线性的，因此，时间复杂度O(n)。1isumjsumajikk10月算法在线班29/50思考 若除了输出最大子数组的和，还需要输出最大子数组本身，应该怎么做？10月算法在线班30/50参考代码10月算法在线班31/50最大间隔 给定整数数组A0N-1，求这N个数排序后最大间隔。如：1,7,14,9,4,13的最大间隔为4。排序后：1,4,7,9,13,14，最大间隔是13-9=4 显然，对原数组排序，然后求后项减前项的最

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

13、时，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月算法在线班35/50Code10月算法在线班36/50字符串的全排列 给定字符串S0N-1，设计算法，枚举S的全排列。10月算法在线班37/50递归算法 以字符串1234为例：1 234 2 134 3 214 4 231 如何保证不遗漏 保证递归前1234的顺序不变10月算法在线班3

14、8/50递归Code10月算法在线班39/50如果字符有重复 去除重复字符的递归算法 以字符1223为例：1 223 2 123 3 221 带重复字符的全排列就是每个字符分别与它后面非重复出现的字符交换。即：第i个字符(前)与第j个字符(后)交换时，要求i,j)中没有与第j个字符相等的数。10月算法在线班40/50Code10月算法在线班41/50重复字符的全排列递归算法时间复杂度 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)2 f(n)

15、=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月算法在线班42/50空间换时间10月算法在线班43/50空间换时间的方法 如果是单字符，可以使用mark256；如果是整数，可以遍历整数得到最大值max和最小值min，使用markmax-min+1；如果是浮点数或其他结构，考虑使用Hash。事实上，如果发现整数间变化太大，也应该考虑使用Hash；可以认为整数/字符的情况是最朴素的Hash。10月算法在线班44/50全排列的非递归算法 起点：字典序最小的

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

17、1；查找(小大)：Si+1N-1中比Ai大的最小值Sj；交换：Si，Sj；翻转：Si+1N-1思考：交换操作后，Si+1N-1一定是降序的 以926520为例，考察该算法的正确性。10月算法在线班47/50非递归算法Code10月算法在线班48/50几点说明 下排列算法能够天然解决重复字符的问题！不妨还是考察926520的下一个字符串 STL在Algorithm中集成了next_permutation 可以将给定的字符串A0N-1首先升序排序，然后依次调用next_permutation直到返回false，即完成了非递归的全排列算法。10月算法在线班49/50我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班50/50感谢大家恳请大家批评指正！