15. 二维数组中的查找

本文最后更新于:2022年8月1日 凌晨

问题描述

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。

请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

样例

1
2
3
4
5
6
7
8
9
10
11
12
输入数组:

[
[1,2,8,9]
[2,4,9,12]
[4,7,10,13]
[6,8,11,15]
]

如果输入查找数值为7,则返回true

如果输入查找数值为5,则返回false

解决方案

利用数组的特点,从第一行开始,我们每次让数组的每行的最后一个和目标值进行比较。具体算法如下:

  1. 行序列 i 初始化为0,列序列 j 初始化为数组的列数;
  2. 写一个while循环判断: array[i][j] 和 target 的大小关系:
  • array[i][j] < target, 说明这一行的数都比较目标值小,则意味着行序列需要增加;
  • array[i][j] > target, 说明目标值可能就在这行,我们让列序列减小;
  • array[i][j] = target, 那就说明找到了,返回True就好了
  1. 如果while循环都走完了,则只能说明这个数组中没有这个数,返回False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def searchArray(self, array, target):
"""
:type array: List[List[int]]
:type target: int
:rtype: bool
"""

len_line = len(array) - 1
if len_line <1:
return False
len_column = len(array[0])-1
i = 0
j = len_column
while i <= len_line and j >= 0:
if array[i][j] < target:
i += 1
elif array[i][j] > target:
j -= 1
else:
return True
return False

15. 二维数组中的查找
https://yance.wiki/15. 二维数组中的查找/
作者
Yance Huang
发布于
2019年6月1日
许可协议