博客

【

题目要求

】：

杨氏矩阵

有一个二维数组.

数组的每行从左到右是递增的，每列从上到下是递增的.

在这样的数组中查找一个数字是否存在。

时间复杂度小于O(N);

数组：

1 2 3

2 3 4

3 4 5

1 3 4

2 4 5

4 5 6

1 2 3

4 5 6

7 8 9

【

解题思路

】：

杨氏矩阵就是例如上面这样每一行每一列都是递增的矩阵。而在C语言中，我们可以把它定义为一个二维数组。只要把二维数组中每个值和目标值相比较，就能知道能不能找到这个元素。

但是题目还要求时间复杂度小于O(N)，所以我们就不能一个一个的对比。

那我们可以发现，右上角和左下角的这两个数是最高效率的查找开始点。我们用上面第三个数组举例：因为右上角的3是第一行里最大的元素，是第三列里最小的元素。而左下角的7又恰好是第三行最小的元素，是第一列最大的元素。我们为什么会选择这两个数来比较呢？是因为，假如我们选择3，那么将3与目标值进行比较，如果目标值大于3，就证明不在第一行，一下子砍掉了一行，如果小于3，就证明不在第三列，也能砍掉一列。这样子来循环比较是很高效的。

【

参考代码

】：

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define ROW 3
#define COL 3
int Findnum(int arr[ROW][COL], int row, int col, int key) {
 int left = 0;
 int right = col - 1;
 while ((left >= 0) && (right < col)) {
  //如果这个数字小于key，则向后移一位；
  if (arr[left][right] < key) {
   left++;
  }
  //如果这个数字大于key，则向前移一位；
  if (arr[left][right] > key) {
   right--;
  }
  //如果这个数字等于key，则返回1；
  if (arr[left][right] == key) {
   return 1;
  }
 }
 //否则返回1；
 return 0;
}
int main() {
 //定义一个二维数组；
 int arr[ROW][COL] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 printf("请输入要查找的数字：");
 int key = 0;
 scanf("%d", &key);
 //找到了返回1,找不到返回0；
 int ret = Findnum(arr, ROW, COL, key);
 if (1 == ret)
 {
  printf("找到了！\n");
 }
 if (0 == ret)
 {
  printf("找不到!\n");
 }
 system("pause");
 return 0;
}