1.题目要求
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在,要求算法复杂度是O(n)。(注:不一定是n*n的矩阵)
举例:
1 2 3 4
2 3 4 5
6 7 8 9
5 6 7
10 11 12
12 13 15
2.思路
思路1:也是最容易想到的,依次遍历这个二维数组,虽然不满足题目O(N)的复杂度需求,但是可以满足基本需求.
改进:我们知道,整个矩阵最大的数在右下角,最小的数在左下角,根据题目需求,假设我要找的数比第一列最右边的数大,那就跳到下一行寻找,假设小,就向左寻找.
举例:
1 6 10 15
7 10 12 16
11 20 21 33
13 21 22 34
假设我要寻找12
假设我要寻找13
3.参考代码
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> //杨氏矩阵 #define COL 4 int YangSearch(int arr[][COL], int row, int col, int key) { int i = 0; int j = col - 1; if (key <arr[0][0] || key>arr[row - 1][col - 1]) return 0; while (i < row && j >= 0) { if (arr[i][j] > key) { j--; } else if (arr[i][j] < key) { i++; } if (arr[i][j] == key) { return 1; //找到了 } } return 0; //找不到 } int main() { int arr[][4] = { {1,6,10,15},{7,10,12,16},{11,20,21,33},{13,21,22,34} }; int a = YangSearch(arr, 4, 4, 20); return 0; }
