面試-常考的數(shù)據(jù)結(jié)構(gòu)題-在線瀏覽
2025-07-25 22:51本頁(yè)面
【正文】 while(cur) { } headnext = NULL。}還有一種利用遞歸的方法。源代碼如下。因?yàn)橐淖僪ead指針，所以我用了引用。 head){ if(p == NULL || pnext == NULL) { } else { }}3,判斷兩個(gè)數(shù)組中是否存在相同的數(shù)字 給定兩個(gè)排好序的數(shù)組，怎樣高效得判斷這兩個(gè)數(shù)組中存在相同的數(shù)字？這個(gè)問題首先想到的是一個(gè)O(nlogn)的算法。用C++實(shí)現(xiàn)代碼如下： bool findmon(int a[],int size1,int b[],int size2){ int i。isize1。 int start=0,end=size21,mid。 while(start=end) if(a[i]==b[mid]) else if (a[i]b[mid]) else}后來發(fā)現(xiàn)有一個(gè) O(n)算法。所以只要一次遍歷就行了。推進(jìn)的規(guī)則是比較兩個(gè)數(shù)組中的數(shù)字，小的那個(gè)數(shù)組的下標(biāo)向前推進(jìn)一步，直到任何一個(gè)數(shù)組的下標(biāo)到達(dá)數(shù)組末尾時(shí)，如果這時(shí)還沒碰到相同的數(shù)字，說明數(shù)組中沒有相同的數(shù)字。 while(isize1 amp。 jsize2) { } return false。對(duì)于這個(gè)問題，最簡(jiǎn)單也是最容易想到的那就是窮舉所有子序列的方法。當(dāng)然算法復(fù)雜度會(huì)達(dá)到O(n^3)。 在給出線性算法之前，先來看一個(gè)對(duì)窮舉算法進(jìn)行優(yōu)化的算法，它的算法復(fù)雜度為O(n^2)。假設(shè)Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。 for(i=0。i++) {jsize。 { v=v+a[j]
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1