欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-09 18:04:23
剑指Offer积累-JZ1-二维数组中的查找为了提升个人能力,开始积累算法,从剑指Offer开始。以下是自己做的笔记&记录,欢迎提出意见或指正错误。题目描述在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。示例1输入7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]返回值true方法一:顺序查...

剑指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)

方法二:二分查找

在二维数组中选择合适位置开始查找,因为数组按序排列,可从左下(或右上)开始查找,大于目标值,删除一行(列);小于目标值,删除一列(行)。此例如下图:
剑指Offer积累-JZ1-二维数组中的查找
剑指Offer积累-JZ1-二维数组中的查找
第一种代码思路(右上)

# -*- 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