面试题1 二维数组中的查找

116 阅读 0 评论 77 点赞

我是靠谱客的博主英勇未来，这篇文章主要介绍面试题1 二维数组中的查找，现在分享给大家，希望可以做个参考。

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

leetcode #240

解题：

首先判断是不是空数组，空数组做出异常处理。

假设数组是n*m,先从数组的（0，m-1）也就是右上角的元素开始比较，

if target < arr[i][j]:
那么这一列都大于target，直接 j-=1；

if target > arr[i][j]:
那么target存在的候选列就在j列且行数比i大，i+= 1

if target == arr[i][j]: 找到目标。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# -*- coding:utf-8 -*-
import sys
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here

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

#在python console中运行读入参数时
if __name__ == '__main__':
    n= int(sys.stdin.readline().strip())
    target = int(sys.stdin.readline().strip())
    array = []
    for i in range(n):
        arr2 =sys.stdin.readline().strip().split(' ')
        array.append([int(x) for x in arr2])
    print(target, array)
    res = Solution().Find(target, array)
    print(res)