Search in 2D array
1. Link
2. 描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。[ [1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15] ]
给定 target = 7,返回 true。
给定 target = 3,返回 false。
示例1
输入:
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
复制返回值:
true
复制说明:
存在7,返回true
示例2
输入:
3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
复制返回值:
false
复制说明:
不存在3,返回false
3. 思路
search from the upper left corner, since element < current element on the left, element > current element on the bottom
case 1: if current element < target -> row += 1
case 2: if current element > target -> column -= 1
Otherwise, return true if target is found
4. Coding
class Solution:
# array 二维列表
def Find(self, target, array):
#
#input: target int, 2D array, output: boolean
# idea: binary search
# search from upper left corner
# since element < cur on the left, >cur on the bottom, so
# check current element:
# case 1: if current clement < target ->search bottom
# case 2: if current elemtn > target -> search left side
if not array or not array[0] or target == None:
return False
r, c = 0, len(array[0])-1
while c >=0 and r < len(array):
if array[r][c] <target:
r += 1
elif array[r][c] >target:
c -= 1
else:
return True
return False
Last updated
Was this helpful?