在一个二维数组中,每一行都从左到右递增,每一列都从上到下递增,在这样一个数组里查找一个数
更新:HHH   时间:2023-1-7


第一种:

思路:

二维数组是从左到右递增,从上到下递增,row为行数,col为列数,a[row-1][col-1]为最大数,如果剔除这一行,这一列,则最大数为a[row-2][col-2],如果要查找的num大于a[row-2][col-2]并且大于a[row-1][col-1],则在该row-1行和col-1列查找,照这样遍历。


这样太麻烦,效率太低,应当舍弃。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//二维数组传参
bool find(int (*a)[7],int M,int num)
{
assert(a);
int i=M-1;
int j=6;
if(num<a[0][0]||num>a[i][6])
{
return false;
}
else
{
while((j>0)&&(i>0))
{
if(num==a[i][j])
{
return false;
}
               if(num<a[i][j]&&num<a[i-1][j-1])
  {

  int tmp=0;
  for(;tmp<j;j++)
  {
                      if(a[i][tmp]==num)
 {
 return true;
 }
  }
  tmp=0;
  for(;tmp<i;tmp++)
  {
  if(a[tmp][j]==num)
  {
  return true;
  }
  }
  return false;
  }
  else 
  {
  j--;
  i--;
  }
}
if(i==0)
{
for(int tmp=0;tmp<j;tmp++)
{
if(a[i][tmp]==num)
{
return true;
}
}
return false;
}
if(j=0)
{
for(int tmp=0;tmp<i;tmp++)
{
if(a[tmp][i]==num)
{
return true;
}
}
return false;
}
}

}
int main()
{
int a[4][7]={
{1,2,3,4,5,6,7},
{3,4,5,6,7,8,9},
{5,7,9,11,13,15,17},
{7,9,13,15,17,21,23},
};
printf("%d\n",find(a,4,1));
system("pause");
return 0;
}

第二种:

思路:实现比较简单,建议采用。

从右上角访问,该数组从左到右递增,从上到下递增,a[0][col-1]和num比较,如果num比a[0][col-1]大,则剔除该行,row--,如果num比a[0][col]小,则剔除该列,col--;缩小查找范围。


左下角访问道理一样。

#include<stdio.h>
#include<stdlib.h>
bool find(int (*a)[7],int row,int num)
{
	int i=0;
	int col=7;
	int j=col-1;
	while(i<row&&j>=0)
	{
		if(a[i][j]==num)
		{
			return true;
		}
		else if(a[i][j]<num)
		{
			i++;
		}
		else 
		{
			j--;
		}
	}
	return false;
}
int main()
{
	int a[4][7]={
	{1,2,3,4,5,6,7},
	{3,4,5,6,7,8,9},
	{5,7,9,11,13,15,17},
	{7,10,13,15,17,21,23},
	};
	printf("%d\n",find(a,4,34));
	system("pause");
	return 0;
}


返回编程语言教程...