算法题数组

‘壹’ 算法-面试题系列 - 求数组左部分最大值减去右部分最大值的绝对值

给定一个数组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)。