博客

题目：在一个二维数组中，

每一行都按照从左到右递增的顺序排序

，

每一列都按照从上到下递增的顺序排序

。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。时间复杂度 O(row+col)

//数组样例：

int arr[4][4] = {


1,2,8,9,

2,4,9,12,

4,7,10,13,

6,8,11,15

};

解题思路：

第一种：从左下角访问，因为该数组是从左到右递增，从上到下递增，所以将输入的整数x与arr[row-1][0]比较，如果x大于arr[row-1][0]，剔除该列 col++。如果x小于arr[row-1][0]，剔除该行 row–，以此来缩小范围。

第二种：从右上角访问，因为该数组是从左到右递增，从上到下递增，所以将输入的整数x与arr[0][col-1]比较，如果x大于arr[0][col-1]，剔除该行 row++。如果x小于arr[0][col-1]，剔除该列 col–，以此来缩小范围。

//此代码为从左下角访问
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <windows.h>
#define ROW 4
#define COL 4
#define true 1
#define false 0
Find_Val(int arr[ROW][COL], int row, int col, int x)
{
	int i = row - 1;                      
	int j = 0;
	for (j = 0; i >= 0 && j < col;){
		if (x > arr[i][j]){
			j++;
			continue;
		}
		else if (x < arr[i][j]){
			i--;
			continue;
		}
		else{
			return true;
		}
		return false;
	}
}
int main()
{
	int arr[ROW][COL] = { 1, 2, 8, 9, 2, 4, 9, 12, 4, 7, 10, 13, 6, 8, 11, 15 };
	printf("请输入数组: ");
	for (int i = 0; i < ROW; i++){
		for (int j = 0; j < COL; j++){
			printf("%d ", arr[i][j]);
		}
	}
	printf("\n");
	while (1){
		printf("请输入一个整数: ");
		int x = 0;
		scanf("%d", &x);
		Find_Val(arr, ROW, COL, x);
		if (Find_Val(arr, ROW, COL, x) == true){
			printf("数组中含有该数字\n");
		}
		else{
			printf("数组中不含该数字\n");
		}
	}
	system("pause");
	return 0;
}

运行截图如下：

如果想从右上角访问，只需在Find_Val函数中做一些改动即可，如下图所示：

Find_Val(int arr[ROW][COL], int row, int col, int x)
{
	int i = 0;
	int j = col - 1;
	for (i = 0; i < row&&j >= 0;){
		if (x > arr[i][j]){
			i++;
			continue;
		}
		else if (x < arr[i][j]){
			j--;
			continue;
		}
		else{
			return true;
		}
		return false;
	}
}