本文主要是介绍常见面试题：二维递增数组的快速查找，复杂度（M+N-2）,M,N分别为数组的行数和列数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：一个二维数组，按行按列都是递增的，要求程序在尽可能小的复杂度的情况下查找给定的元素。
例如：a[4][5]={
{1, 3, 7, 11, 19},
{2, 7, 10, 29, 30},
{13, 28, 54, 69, 90},
{46, 57, 78, 98, 101}
}查找29，返回其下标（1,3）。
思路：需要充分利用数组的特点，按行按列都是递增的，这样才能减小复杂度。
下面就找一下特点喽，按行按列递增这是最明显的，还有隐含一点的就是，左上角和右下角分别是最小和最大的元素。恩，对的。哪还有呢？我们需要的是简便算法呀！继续看的话会发现，一列的最大元素在对应的最后一行，（废话），一行的最小一个在最左边。如果一个元素比一列的最下面一个元素还大的话，那它就一定不在这一列。诶，有点眉目了。如果要查找的元素比第一列的最下面一个元素还大的话，那它一定在之后的数组中。同理，目标如果比这个元素小的话，那它一定不在此行，且在上面的几行里。哈哈，数组又缩小了。然后，我们每次都能排除一行或一列，最难找的那个元素就是右上角的了。那它的复杂度是多少那？折线走过去，就是M-1+N-1，对啊，线性哎，不错1
//c语言
#include <stdio.h>
/*a是按行按列均递增的数组，该函数实现在数组中找出目标数据的下标，M和N表示数组的行数和列数*/
/*注：未考虑数组合法与否，返回的是数组的下标*/
int getIndexofIncArray(int *a, int M, int N, int target, int *x, int *y){int i=0, j = M-1, count;//找不到元素的话返回-1，找到的话返回0,i表示列*x = *y = -1;//初始化for(count=0; count<N+M;count++){printf("第%d次访问:%d\n",count, *(a + N*j + i));if(target == *(a + N*j + i)){*x = j;*y = i;return 0;}else if(target > *(a + N*j + i)){//目标大于，右移if((i >= N) && (j < 0)){break;}else{i++;}}else{if((i >= N) && (j < 0)){break;}else{//目标小于，上移j--;}}}return -1;
}void main(){int i, j;int *p1 = &i, *p2 = &j;int a[4][5]={{1, 3, 7, 11, 19},{2, 7, 10, 29, 30},{13, 28, 54, 69, 90},{46, 57, 78, 98, 101}};getIndexofIncArray(&a[0][0], 4, 5, 19, p1, p2);printf("%d, %d", i, j);getchar();
}这篇关于常见面试题：二维递增数组的快速查找，复杂度（M+N-2）,M,N分别为数组的行数和列数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
