剑指Offer积累-JZ1-二维数组中的查找

为了提升个人能力，开始积累算法，从剑指Offer开始。

---

以下是自己做的笔记&记录，欢迎提出意见或指正错误。

题目描述

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

示例1
输入
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值
true

方法一：顺序查找

暴力法，遍历所有元素，直到找到为止。时间复杂度较高o（n*n）

# -*- coding:utf-8 -*-
class Solution:
#     python语言：纯面向对象：
#     三个特性：封装，继承，多态
# python好处：方法库特别多
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for i in array:
            for j in i:
                if target == j:
                    return True
        else:
            return False
                
#     array = [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
#     target = 7
#     status = Find(target, array)

方法二：二分查找

在二维数组中选择合适位置开始查找，因为数组按序排列，可从左下（或右上）开始查找，大于目标值，删除一行（列）；小于目标值，删除一列（行）。此例如下图：


第一种代码思路（右上）

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
            # array 二维列表
#len()函数
#1：作用：返回字符串、列表、字典、元组等长度
#2：语法：len(str)
#3：参数：str：要计算的字符串、列表、字典、元组等
#4：返回值：字符串、列表、字典、元组等元素的长度
#5：实例  5.1、计算字符串的长度：5.2、计算列表的元素个数：5.3、计算字典的总长度(即键值对总数)：5.4、计算元组元素个数：

        row = len(array)
        col = len(array[0])
        i = 0
        j = col - 1
        while i < row and j >= 0:    #给出不能越界的条件
            if target == array[i][j]:
                return True
            elif target < array[i][j]:
                j = j - 1
            else:
                i = i + 1
        return False  

第二种代码思路（左下）

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self,target, array):
        # write code here
        if array and array[0]:
            raw = len(array) - 1
            col = 0
            while target != array[raw][col]:#不等于就要判断删除行列;等于，循环条件不满足直接跳出，返回true
                if target > array[raw][col]:
                    col += 1
                    if col >= len(array[0]):#判断是否超过数组长度
                        return 0
                if target < array[raw][col]:
                    raw -= 1
                    if raw < 0:#判断是否超过数组长度
                        return 0
            return 1
        else:
            return 0

这两种方法循环和判断逻辑有一些差别，有运算选第一种思路，有列表选第二种思路。
【代码优化思路：占用最少空间，缩短时间。减少空间，少定义变量；缩短时间，减少循环 while 和 for】

本文地址：https://blog.csdn.net/chuli666/article/details/109911534