第一節(jié)、尋找和為定值的兩個數(shù)

? ? ? ? 題目：輸入一個數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。要求時間復(fù)雜度是O(n)。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。

? ? ? ??例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。

?

??? 思路如下：

??? 1：直接窮舉，從數(shù)組中任意選取兩個數(shù)，判定它們的和是否為輸入的那個數(shù)字。此舉復(fù)雜度為O(n^2) 。很顯然，我們要尋找效率更高的解法。

?

??? 2:題目相當(dāng)于，對每個a[i]，查找sum-a[i]是否也在原始序列中，每一次要查找的時間都要花費(fèi)為O(n)，這樣下來，最終找到兩個數(shù)還是需要O(n^2) 的復(fù)雜度。那如何提高查找判斷的速度呢？

??? 答案是二分查找。二分查找的時間復(fù)雜度為O(lg n)?，如果原數(shù)組有序，直接二分查找，n個數(shù)的總時間為O(n lg n) ；如果原數(shù)組無序，則需要先排序后二分，復(fù)雜度同樣為O(nlgn + nlgn) =O(nlgn) ，空間復(fù)雜度為O(1) 。

???

??? 3：有沒有更好的辦法呢？可以依據(jù)上述思路2的思想，進(jìn)一步縮小查找時間。如果數(shù)組無序，則先在O(nlgn)?時間內(nèi)排序。

??? 舉個例子，如下：

原始序列：1、 2、 4、 7、11、15????

??? 用輸入數(shù)字15減一下各個數(shù)，得到對應(yīng)的序列為：

對應(yīng)序列：14、13、11、8、4、0?????

??? 第一個數(shù)組以一指針i 從數(shù)組最左端開始向右掃描，第二個數(shù)組以一指針j 從數(shù)組最右端開始向左掃描，誰指的元素小，誰先移動，如果a[*i]=a[*j]，就找出這倆個數(shù)來了。兩端同時查找，時間復(fù)雜度瞬間縮短到了O(n)，但卻同時需要O(n)的空間存儲第二個數(shù)組。

??? 因此，如果原數(shù)組無序，則需要時間O(n +nlgn) =O(nlgn)?；如果原數(shù)組有序，則需要時間O(n) 。

?

??? 4：針對上述思路進(jìn)一步改進(jìn)，使空間復(fù)雜度由O(n)變?yōu)?/span>O(1)。如果數(shù)組是無序的，則先在O(nlgn) 時間內(nèi)排序，然后用兩個指針 i，j，各自指向數(shù)組的首尾兩端，令i=0，j=n-1，逐次判斷a[i]+a[j]?=sum，如果a[i]+a[j]>sum，則要想辦法讓a[i]+a[j]的值減小，所以此刻i不動，j--，如果某一刻a[i]+a[j]<sum，則要想辦法讓a[i]+a[j]的值增大，所以此 刻i++，j不動。所以，數(shù)組無序的時候，時間復(fù)雜度最終為O(n +nlgn)?=O(nlgn)，若原數(shù)組是有序的，則不需要事先的排序，直接O(n)搞定，且空間復(fù)雜度還是O(1) ，此思路是相對于上述所有思路的一種改進(jìn)。

?

??? 5：還可以構(gòu)造hash表，正如編程之美上的所述，給定一個數(shù)字，根據(jù)hash映射查找另一個數(shù)字是否也在數(shù)組中，只需用O(1) 的時間，這樣的話，總體的算法通上述思路3 一樣，也能降到O(n) ，但有個缺陷，就是構(gòu)造hash額外增加了O(n) 的空間，不過，空間換時間，仍不失為在時間要求較嚴(yán)格的情況下的一種好辦法。

?

??? 所以，要想達(dá)到時間O(n) ，空間O(1) 的目標(biāo)，除非原數(shù)組是有序的（指針掃描法），不然，當(dāng)數(shù)組無序的話，就只能先排序，后指針掃描法或二分查找（時間O(nlgn) ，空間O(1) ），或映射或hash（時間O(n) ，空間O(n) ）。時間或空間，必須犧牲一個。

?

二：二分查找

??? “二分查找可以解決已排序數(shù)組的查找問題：只要數(shù)組中包含T（即要查找的值），那么通過不斷縮小包含T的范圍，最終就可以找到它。一開始，范圍覆蓋整個數(shù)組。將數(shù)組的中間項(xiàng)與T進(jìn)行比較，可以排除一半元素，范圍縮小一半。就這樣反復(fù)比較，反復(fù)縮小范圍，最終就會在數(shù)組中找到T，或者確定原以為T所在的范圍實(shí)際為空。對于包含N個元素的表，整個查找過程大約要經(jīng)過logN次比較。

??? 多數(shù)程序員都覺得只要理解了上面的描述，寫出代碼就不難了；但事實(shí)并非如此。我在貝爾實(shí)驗(yàn)室和IBM的時候都出過這道考題。那些專業(yè)的程序員有幾個小時的時間，可以用他們選擇的語言把上面的描述寫出來。考試結(jié)束后，差不多所有程序員都認(rèn)為自己寫出了正確的程序。于是，我們花了半個鐘頭來看他們編寫的代碼經(jīng)過測試用例驗(yàn)證的結(jié)果。幾次課，一百多人的結(jié)果相差無幾：90%的程序員寫的程序中有bug（我并不認(rèn)為沒有bug的代碼就正確）。

??? 我很驚訝：在足夠的時間內(nèi)，只有大約10%的專業(yè)程序員可以把這個小程序?qū)憣Α５珜懖粚@個小程序的還不止這些人：高德納在《計算機(jī)程序設(shè)計的藝術(shù) 第3卷 排序和查找》第6.2.1節(jié)的“歷史與參考文獻(xiàn)”部分指出，雖然早在1946年就有人將二分查找的方法公諸于世，但直到1962年才有人寫出沒有bug的二分查找程序。”——喬恩·本特利，《編程珠璣（第1版）》第35-36頁。

?

??? 二分查找算法的邊界,一般來說分兩種情況,一種是左閉右開區(qū)間,類似于[left, right),一種是左閉右閉區(qū)間,類似于[left, right].需要注意的是, 循環(huán)體外的初始化條件,與循環(huán)體內(nèi)的迭代步驟, 都必須遵守一致的區(qū)間規(guī)則,也就是說,如果循環(huán)體外初始化時,是以左閉右開區(qū)間為邊界的,那么循環(huán)體內(nèi)部的迭代也應(yīng)該如此.如果兩者不一致,會造成程序的錯誤.比如下面就是錯誤的二分查找算法：

????left?=?0,?right?=?n;

????while?(left?<?right)

????{

????????middle?=?(left?+?right)?/?2;

????????if?(array[middle]?>?v)

????????{

????????????right?=?middle?-?1;

????????}

????????else?if?(array[middle]?<?v)

????????{

????????????left?=?middle?+?1;

????????}

????????else

????????{

????????????return?middle;

????????}

????}

??? 這個算法的錯誤在于, 在循環(huán)初始化的時候,初始化right=n,也就是采用的是左閉右開區(qū)間,而當(dāng)滿足array[middle]> v的條件是, v如果存在的話應(yīng)該在[left,middle)區(qū)間中,但是這里卻把right賦值為middle - 1了,這樣,如果恰巧middle-1就是查找的元素,而且middle-1=left,那么就會找不到這個元素。

?

??? 下面給出兩個算法, 分別是正確的左閉右閉和左閉右開區(qū)間算法,可以與上面的進(jìn)行比較:

int?search2(int?array[],?int?n,?int?v)

{

????int?left,?right,?middle;

????left?=?0,?right?=?n?-?1;

????while?(left?<=?right)

????{

????????middle?=?(left?+?right)?/?2;

????????if?(array[middle]?>?v)

????????{

????????????right?=?middle?-?1;

????????}

????????else?if?(array[middle]?<?v)

????????{

????????????left?=?middle?+?1;

????????}

????????else

????????{

????????????return?middle;

????????}

????}

????return?-1;

}

?

int?search3(int?array[],?int?n,?int?v)

{

????int?left,?right,?middle;

????left?=?0,?right?=?n;

????while?(left?<?right)

????{

????????middle?=?(left?+?right)?/?2;

????????if?(array[middle]?>?v)

????????{

????????????right?=?middle;

????????}

????????else?if?(array[middle]?<?v)

????????{

????????????left?=?middle?+?1;

????????}

????????else

????????{

????????????return?middle;

????????}

????}

????return?-1;

}

???????? 另外：在循環(huán)體內(nèi),計算中間位置的時候,使用的是這個表達(dá)式：

middle?=?(left?+?right)?/?2;

??? 假如,left與right之和超過了所在類型的表示范圍的話,那么middle就不會得到正確的值.所以,更穩(wěn)妥的做法應(yīng)該是這樣的:

middle?=?left?+?(right?-?left)?/?2;

(http://www.cppblog.com/converse/archive/2009/10/05/97905.html)

?

三：編程求解

?????? 輸入兩個整數(shù) n 和 m，從數(shù)列1，2，3.......n 中 隨意取幾個數(shù)，使其和等于 m ,要求將其中所有的可能組合列出來。

?????? 分析：用f(m, n)表示從1到n的序列中，和等于m的所有可能的組合，分幾種情況：

?????? 1：如果m<n，則m+1, m+2,..n這些數(shù)不可能出現(xiàn)在任何組合中，所以：

f(m, n) = f(m, m)。

?????? 2：如果m=n，則單獨(dú)的n是組合之一，所以f(m, n) = 。

?????? 3：如果m>n，則可以根據(jù)組合中是否包含n進(jìn)行區(qū)分，所以：

f(m, n) = 。

?????? 所以，該題目的解法可以用遞歸實(shí)現(xiàn)，考慮到要保存中間結(jié)果以便打印出最終所有的組合，所以可以借用棧實(shí)現(xiàn)，下面的代碼直接使用list來模擬棧的操作：

void findsum(int sum, intn)

{

???????? static list<int> indexStack;?

?

???????? if(sum < 1)return;

???????? if(n < 1)return;

?

???????? if(sum < n)

???????? {

????????????????? return findsum(sum, sum);

???????? }

???????? else if(sum == n)

???????? {

????????????????? cout << sum <<"+";

????????????????? for(list<int>::iteratoriter = indexStack.begin();iter!=indexStack.end();++iter)?

????????????????? {

????????????????????????? cout<<*iter<<"+";?

????????????????? }

????????????????? printf("\b \n");?

????????????????? /*

????????????????????????? \b是退格符，顯示的時候是將光標(biāo)退回前一個字符，

????????????????????????? 但不會刪除光標(biāo)位置的字符，

????????????????????????? 如果后邊有新的字符，將覆蓋退回的那個字符，

????????????????????????? 這與我們在文本編器中按Backspace的效果不一樣。?? ???????? */

????????????????? return findsum(sum, sum-1);

???????? }

???????? else

???????? {

????????????????? indexStack.push_front(n);

????????????????? findsum(sum-n, n-1);

????????????????? indexStack.pop_front();

????????????????? findsum(sum, n-1);

???????? }

}

?

四：最長遞增子序列(LongestIncreasing Subsequence，LIS問題)

?????? 給定一個長度為n的數(shù)組，找出一個最長的單調(diào)遞增子序列（不一定連續(xù)）。 更正式的定義是：

?????? 設(shè)L=<a1,a2,…,an>是n個不同的實(shí)數(shù)的序列，L的遞增子序列是這樣一個子序列Lin=<ak1,ak2,…,akm>，其中k1<k2<…<km且ak1<ak2<…<akm。求最大的m值。

?????? 比如數(shù)組A 為{10, 11, 12, 13, 1,2, 3, 15}，那么最長遞增子序列為{10,11,12,13,15}。

?

1：動態(tài)規(guī)劃(http://blog.chinaunix.net/uid-26548237-id-3757779.html)

?????? 對于數(shù)組a[n], 假設(shè)LIS[i]表示：以a[i]為結(jié)尾的，最長遞增子序列的長度。

?????? 初始情況下，LIS[i]=1，因?yàn)樽铋L遞增子序列只包含a[i];

?????? 如果對于j，0<=j<i，假設(shè)LIS[j]已經(jīng)求解出來了，則可以根據(jù)LIS[j]來計算LIS[i]：對于所有j(0<=j<i)，如果a[i]>a[j]，則LIS[j] + 1的最大值。也就是：

?????? LIS[i]= 。所以，代碼如下：

??????

?????? for(i = 0; i<len; i++)

???????? {

????????????????? LIS[i] = 1;

???????? }

?

???????? for(i = 0; i < len; i++)

???????? {

????????????????? for(j = 0; j < i; j++)

????????????????? {

????????????????????????? if(a[i] > a[j] &&LIS[i]<LIS[j]+1)

????????????????????????? {

?????????????????????????????????? LIS[i] = LIS[j]+1;

????????????????????????? }

????????????????? }

???????? }

?

???????? max = LIS[0];

???????? for(i = 1; i < len; i++)

???????? {

????????????????? printf("the LIS[%d] is %d\n", i, LIS[i]);

????????????????? if(max < LIS[i])

????????????????? {

????????????????????????? max = LIS[i];

????????????????? }

???????? }

?

2：二分查找法(http://www.felix021.com/blog/read.php?1587)

?? 假設(shè)存在一個序列d[1..9]= 2 1 5 3 6 4 8 9 7，可以看出來它的LIS長度為5。

下面一步一步試著找出它。

?????? 我們定義一個序列B，然后令 i = 1 to 9 逐個考察這個序列。B[i]中存儲的是：對于長度為i的遞增子序列的中的最大元素，其中的最小值。也就是長度為i的遞增子序列的最小末尾。

?????? 定義LEN記錄數(shù)組B中，已經(jīng)得到的LIS的值。

?

?????? 首先，把d[1]有序地放到B里，令B[1] = 2，就是說當(dāng)只有1一個數(shù)字2的時候，長度為1的LIS的最小末尾是2。這時Len=1

?

?????? 然后，讀取d[2]，因d[2] < B[1]，所以令B[1] = 1，就是說長度為1的LIS的最小末尾是1，d[1]=2已經(jīng)沒用了，很容易理解吧。這時Len=1

?

?????? 接著，d[3]= 5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是說長度為2的LIS的最小末尾是5，很容易理解吧。這時候B[1..2]= 1, 5，Len＝2

?

?????? 再來，d[4]= 3，它正好加在1,5之間，放在1的位置顯然不合適，因?yàn)?小于3，長度為1的LIS最小末尾應(yīng)該是1，這樣很容易推知，長度為2的LIS最小末尾是3，于是可以把5淘汰掉，這時候B[1..2]= 1, 3，Len =2

?

?????? 繼續(xù)，d[5]= 6，它在3后面，因?yàn)锽[2] = 3, 而6在3后面，于是很容易可以推知B[3]= 6, 這時B[1..3]= 1, 3, 6，還是很容易理解吧？ Len= 3 了噢。

?

?????? 第6個, d[6] = 4，你看它在3和6之間，于是我們就可以把6替換掉，得到B[3]= 4。B[1..3] = 1, 3, 4， Len繼續(xù)等于3

?

?????? 第7個, d[7] = 8，它很大，比4大，嗯。于是B[4]= 8。Len變成4了

?

?????? 第8個, d[8] = 9，得到B[5] = 9，嗯。Len繼續(xù)增大，到5了。

?

?????? 最后一個,d[9] = 7，它在B[3]= 4和B[4] = 8之間，所以我們知道，最新的B[4]=7，B[1..5] = 1, 3,4, 7, 9，Len =5。

?

?????? 于是我們知道了LIS的長度為5。之所以B數(shù)組中記錄遞增子序列的最小末尾，是為了遍歷后續(xù)數(shù)組的時候，盡可能的增加遞增子序列的長度。比如某一時刻B[1]= 1， B[2]=5，說明目前的長度為2的遞增子序列中，最小末尾是5，之后碰到6,7,8，...等數(shù)的時候才會增加遞增子序列的長度。如果碰見了一個數(shù)3，因3<5，所以可以用3替換5：B[2]=3。這樣比如后續(xù)碰到了4，則就能增加遞增子序列的長度了。

?

?????? 然后應(yīng)該發(fā)現(xiàn)一件事情了：在B中插入數(shù)據(jù)是有序的，而且是進(jìn)行替換而不需要挪動——也就是說，我們可以使用二分查找，將每一個數(shù)字的插入時間優(yōu)化到O(logN)~~~~~于是算法的時間復(fù)雜度就降低到了O(nlogn)～！代碼如下：

int BIN_LIS(int *a, intlen)

{

???????? int *b = malloc((len+2) * sizeof(int));

???????? int i;

???????? int max = 0;

???????? int left, right, mid;

?

???????? b[1] = a[0];

???????? max = 1;

???????? for(i = 1; i < len; i++)

???????? {

????????????????? if(a[i] > b[max])

????????????????? {

????????????????????????? max++;

????????????????????????? b[max] = a[i];

????????????????????????? continue;

????????????????? }

?????????????????

????????????????? left = 1;

????????????????? right = max;

?

????????????????? while(left <= right)

????????????????? {?????? //注意下面的邊界條件

????????????????????????? mid = left + (right -left)/2;

????????????????????????? if(b[mid] < a[i])

????????????????????????? {

?????????????????????????????????? left = mid +1;

????????????????????????? }

????????????????????????? else

????????????????????????? {

?????????????????????????????????? right = mid -1;

????????????????????????? }

????????????????? }

???????? ???????? b[left]= a[i];

???????? }

???????? return max;

}

?

五：雙端LIS問題

?????? 問題描述：從一列數(shù)中篩除盡可能少的數(shù)使得從左往右看，這些數(shù)是從小到大再從大到小的。

?????? 思路：這是一個典型的雙端LIS問題。

?????? 對于數(shù)組a，用數(shù)組b記錄從左向右看時的LIS，b[i]表示，以a[i]結(jié)尾的，從a[0]到a[i]之間的LIS。

?????? 用數(shù)組c記錄，從右向左看是的LIS，c[i]表示，以a[i]結(jié)尾的，從a[n-1]到a[i]之間的LIS。

?????? 所以，b[i] + c[i] - 1就表示以i為“頂點(diǎn)”的，滿足題目要求的最長序列。所以n-max{b[i] + c[i] -1}就是題目的解。

??? 這個問題同樣需要輔助數(shù)組LIS, LIS[i]中存儲的是：對于長度為i的遞增子序列的中的最大元素，其中的最小值。也就是遞增子序列的最小末尾。每當(dāng)掃描到數(shù)組元素a[i]時，同LIS中的二分查找一樣，需要找到在LIS中合適的位置，這個位置，也就是b[i]或者c[i]的值。

?

代碼如下(自己寫的，JULY的程序有問題)：

int Double_LIS(int *a,int len)

{

???????? int *Lis = malloc((len+2) * sizeof(int));

???????? int *b = malloc(len * sizeof(int));

???????? int *c = malloc(len * sizeof(int));

????????

???????? int i;

???????? int max = 0;

???????? int left, right, mid;

?

???????? int maxlen = 0;

???????? int index;

????????

???????? Lis[1] = a[0];

???????? max = 1;

???????? b[0] = max;

????????

???????? for(i = 1; i < len; i++)

???????? {

????????????????? if(a[i] > Lis[max])

????????????????? {

????????????????????????? max++;

????????????????????????? Lis[max] = a[i];

????????????????????????? b[i] = max;

????????????????????????? printf("b[%d] is %d\n", i, b[i]);

????????????????????????? continue;

????????????????? }

?????????????????

????????????????? left = 1;

????????????????? right = max;

????????????????? while(left <= right)

????????????????? {

????????????????????????? mid = left + (right - left)/2;

????????????????????????? if(Lis[mid] < a[i])

????????????????????????? {

?????????????????????????????????? left = mid + 1;

????????????????????????? }

????????????????????????? else

????????????????????????? {

?????????????????????????????????? right = mid - 1;

????????????????????????? }

????????????????? }

????????????????? Lis[left] = a[i];

????????????????? b[i] = left;

????????????????? printf("b[%d] is %d\n", i, b[i]);

???????? }

?

?

???????? memset(Lis, 0, (len+2) * sizeof(int));

???????? Lis[1] = a[len-1];

???????? max = 1;

???????? c[len-1] = max;

????????

???????? for(i = len - 2; i >= 0; i--)

???????? {

????????????????? if(a[i] > Lis[max])

????????????????? {

????????????????????????? max++;

????????????????????????? Lis[max] = a[i];

????????????????????????? c[i] = max;

????????????????????????? printf("c[%d] is %d\n", i, c[i]);

????????????????????????? continue;

????????????????? }

?????????????????

????????????????? left = 1;

????????????????? right = max;

????????????????? while(left <= right)

????????????????? {

????????????????????????? mid = left + (right - left)/2;

????????????????????????? if(Lis[mid] < a[i])

????????????????????????? {

?????????????????????????????????? left = mid + 1;

????????????????????????? }

????????????????????????? else

????????????????????????? {

?????????????????????????????????? right = mid - 1;

????????????????????????? }

????????????????? }

????????????????? Lis[left] = a[i];

????????????????? c[i] = left;

????????????????? printf("c[%d] is %d\n", i, c[i]);

???????? }

?

???????? maxlen = 0;

???????? for(i = 0; i < len; i++)

???????? {

????????????????? if(b[i]+c[i] > maxlen)

????????????????? {

????????????????????????? maxlen = b[i]+c[i];

????????????????????????? index = i;

????????????????? }

???????? }

???????? printf("index is %d\n", index);

???????? return len - maxlen + 1;

}

?

(http://blog.csdn.net/v_JULY_v/article/details/6419466)

轉(zhuǎn)載于:https://www.cnblogs.com/gqtcgq/p/7247179.html

總結(jié)

以上是生活随笔為你收集整理的08查找满足条件的n个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。