今日面试题:子序列

给定长度为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

【分析完毕】

本文来自微信:待字闺中,2013-09-04发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。