給定長度為n的整數(shù)數(shù)列：a0,a1,..,an-1，以及整數(shù)S。這個數(shù)列會有連續(xù)的子序列的整數(shù)總和大于S的，求這些數(shù)列中，最小的長度。

又見排序分析

原題

給定大小為n的數(shù)組A，A中的元素有正有負。請給出方法，對其排序，保證：


• 負數(shù)在前面，正數(shù)在后面
• 正數(shù)之間相對位置不變
• 負數(shù)之間相對位置不變

能夠做到時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)么？

分析

這類題目，還有其他的變形，比如，數(shù)組A有奇數(shù)和偶數(shù)，排序奇數(shù)在前偶數(shù)在后，并且奇數(shù)和偶數(shù)內(nèi)部的相對順序不能變。那么這類的題目，該如何解決呢？

首先，暴力法可行：從左到右掃描數(shù)組，遇到***個負數(shù)，與其前面的每一個元素進行交換，直到***個位置，這里并不能直接交換， 因為這樣就改變了正數(shù)的相對位置了。后面的繼續(xù)掃描，第二個負數(shù)，依次交換到第二個位置。依次類推。算法總的時間復(fù)雜度為O(n^2)。

上面這個方法，大多數(shù)同學，都可以給出。那么，是否有更快的方法呢？大家請看下面的方法：統(tǒng)計負數(shù)的個數(shù)，設(shè)為M

• 找到索引k>M的***個負數(shù)
• 使用i和j兩個索引，i從0開始，直到遇到***個正數(shù)，j從k開始，直到遇到***個負數(shù)。交換i，j位置上的數(shù)，然后符號取反
• 對于A[0,M]和A[M, n]分別執(zhí)行上面三步
• 修正符號：前面的M個為負數(shù)，后面的為正數(shù)。

下面舉例來說明，對于數(shù)組{-1,1,3,-2,2}，根據(jù)描述，有M=2，k=3。i遇到***個正數(shù)為A1=1，j 遇到***個負數(shù)為A[3]=-2。然后交換i和j位置上的值， 數(shù)組變?yōu)閧-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)的方法是有的。但是，方法過于復(fù)雜。這類問題，可以統(tǒng)稱為 stable 0-1 sorting。還是蠻有意思的。大家感興趣的話，可以參考下面的文章：http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/KP92b.pdf

原文鏈接：http://www.ituring.com.cn/article/56013