演算法題數組

『壹』 演算法-面試題系列 - 求數組左部分最大值減去右部分最大值的絕對值

給定一個數組arr長度為N，你可以把任意長度大於0且小於N的前綴作為左部分，剩下的作為右部分。

但是每種劃分下都有左部分的最大值和右部分的最大值

請返回最大的， 左部分最大值減去右部分最大值的絕對值 。

演算法流程

我們要求左邊最大減去右邊最大，max肯定是在左邊數組和右邊數組中的最後參與決策的最大數。

假設12在左邊數組中，右邊數組剩下[5,6,7]

因為把max放入了左邊的數組，所以， 我們需要右邊數組的最大值盡可能的小 ，數組個數越少，他的最大值就是盡可能的小，比如剩下[5,6,7]的情況，我們可以看到我們區arr[N-1]這個數作為右側數組，是最滿足 左部分最大值減去右部分最大值的絕對值 條件的。

同理 把max劃分到右側數組，左側數組a[0]劃分是最符合條件的。

『貳』 演算法題，請給出下面二維數組的排序演算法

#include <stdio.h> #include <stdlib.h>#include <time.h> #define LINE 10 //預定義二維數組行數#define COLUMN 10 //列數void bubble_sort(int a[], int n){ int i, j, temp; for (j = 0; j < n; j++) for (i = j+1; i< n ; i++) { if(a[i] < a[j]) { temp = a[i]; a[i] = a[j]; a[j] = temp; } }} int main(){ int arr[LINE][COLUMN]={0}; int i,j,k; srand((unsigned)time(NULL));//初始化隨種子 for (i = 0; i != LINE; i++) { for(j=0;j!=COLUMN;++j){ //逐行輸入數據 arr[i][j]=rand()%1000+1;//利用隨機數生成1000以內整數，方便調試 //scanf("%d",&arr[i][j]);//手工輸入測試數據 } bubble_sort(arr[i], COLUMN);//輸入完一行，就對該行進行排序 } for (i = 0; i != LINE; i++)//輸出排序後結果 { for(j=0;j!=COLUMN;++j){ printf("%4d ",arr[i][j]); } printf("\n"); } return 0;}

『叄』 關於數組演算法的問題

二分該數的位置
輸入數設為x，數組設為a,數組長度為n
若我們取a[mid]與x比較

由於a是升序的，a[mid]前面的數都比a[mid]小，所以若x>a[mid] 則x>a[mid]前面的所有數，我們想要的答案就在區間[mid+1, n]。
反之答案與[1,mid-1]之間，若a[mid]=x,就退出演算法（找到答案），若a[mid]<x且a[mid+1]>x,則x相鄰角標也已找到，就為mid與mid+1.
分析這個演算法的時間復雜度，
判斷答案在不在[l,r]中，取mid=（l+r）/2.這樣花O(1)判斷後即可鎖定答案在[l,mid-1]還是在[mid+1,r]
這樣設規模為n的問題時間耗費為T(n)
則由演算法過程可知：T(n)=O(1)+T(n/2) , T(1)=O(0)
n=2時，T（2）=O（1）+O（0）=O（1）
n=4時，T（4）=O（1）+O（1）=O（2）
n=8時，T（8）=O（1）+O（2）=O（3）
可發現
0=log2(1),
1=log2(2),
2=log2(4),
3=log2(8).
用數學歸納法（詳見《數據結構與演算法初步》中「分治演算法的時間復雜度計算」）即可證明該演算法時間復雜度為O(log2(n)).

順便給份代碼(c++）：
#include<cstdio>
int main(){
int a[100005]={0,2,3,4,66,456,2222},n=6,x=1,ans,ret;//位置0按中國習慣不放數。
int l=1,r=6,mid;//搜索區間[1,6]
while(l<=r){
mid=(l+r)>>1;
if(a[mid]==x){ ans=mid;break; }
if(a[mid]<x && a[mid+1]>x){ ret=mid;break; }
if(a[mid]<x) l=mid;
else r=mid;
}
if(ans) printf("%d",ans);
else printf("%d %d",ret,ret+1);
}
注意，若查詢的數沒有前一個或後一個數，則會出錯
如果為了簡潔，用下面這個：
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int a[100005]={0,2,3,4,66,456,2222},n=6,x=567,ans,ret;//位置0按中國習慣不放數。
ans=lower_bound(a+1,a+7,x)-a;
if(a[ans]==x) printf("%d",ans);
else printf("%d %d",ans-1,ans);
}
lower_bound返回（升序）數組中第一個大於等於x的數的指針

『肆』 KMP演算法求next數組的問題

字元串如果是以0為下標的話next[7]是0，只有最後一位與第一位相等。

在第i個字元前面的i-1個字元裡面，

從開頭開始的1個字元與最後1個字元是否相等，若不是，則next[i]=0；

從開頭開始的2個字元與最後2個字元是否相等，若不是，則next[i]=1；

從開頭開始的3個字元與最後3個字元是否相等，若不是，則next[i]=2；

前綴next數組的求解演算法：

void SetPrefix(const char *Pattern, int prefix[])

{

int len=CharLen(Pattern);//模式字元串長度。

prefix[0]=0;

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

{

int k=prefix[i-1];

//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推。

(4)演算法題數組擴展閱讀：

kmp演算法完成的任務是：給定兩個字元串O和f，長度分別為n和m，判斷f是否在O中出現，如果出現則返回出現的位置。常規方法是遍歷a的每一個位置，然後從該位置開始和b進行匹配，但是這種方法的復雜度是O(nm)。kmp演算法通過一個O(m)的預處理，使匹配的復雜度降為O(n+m)。