今日面试题：子序列

给定长度为n的整数数列：a0,a1,..,an-1，以及整数S。这个数列会有连续的子序列的整数总和大于S的，求这些数列中，最小的长度。

又见排序分析

原题

给定大小为n的数组A，A中的元素有正有负。请给出方法，对其排序，保证：


• 负数在前面，正数在后面
• 正数之间相对位置不变
• 负数之间相对位置不变

能够做到时间复杂度为O(n)，空间复杂度为O(1)么？

分析

这类题目，还有其他的变形，比如，数组A有奇数和偶数，排序奇数在前偶数在后，并且奇数和偶数内部的相对顺序不能变。那么这类的题目，该如何解决呢？

首先，暴力法可行：从左到右扫描数组，遇到***个负数，与其前面的每一个元素进行交换，直到***个位置，这里并不能直接交换， 因为这样就改变了正数的相对位置了。后面的继续扫描，第二个负数，依次交换到第二个位置。依次类推。算法总的时间复杂度为O(n^2)。

上面这个方法，大多数同学，都可以给出。那么，是否有更快的方法呢？大家请看下面的方法：统计负数的个数，设为M

• 找到索引k>M的***个负数
• 使用i和j两个索引，i从0开始，直到遇到***个正数，j从k开始，直到遇到***个负数。交换i，j位置上的数，然后符号取反
• 对于A[0,M]和A[M, n]分别执行上面三步
• 修正符号：前面的M个为负数，后面的为正数。

下面举例来说明，对于数组{-1,1,3,-2,2}，根据描述，有M=2，k=3。i遇到***个正数为A1=1，j 遇到***个负数为A[3]=-2。然后交换i和j位置上的值， 数组变为{-1, -2, 3, 1, 2}, 然后改变符号，得到{-1,2,3,-1,2}。然后递归处理{-1,2},{3,-1,2}，最终得到{-1,2,1,-3,2}。进行***一步，修正 符号, 得到{-1,-2,1,3,2}。即为最终答案。这个方法是nlog(n)的，比上面的提高了一些。

但是上面的方法，仍旧不是O(n)的。那么O(n)的方法，是否存在呢？我们认为，接近O(n)的方法是有的。但是，方法过于复杂。这类问题，可以统称为 stable 0-1 sorting。还是蛮有意思的。大家感兴趣的话，可以参考下面的文章：http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/KP92b.pdf

当前标题：今日面试题：子序列
网站路径：http://www.mswzjz.cn/qtweb/news39/339589.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能