原创

【剑指offer】01——二维数组中的查找 (数组)

前言

本文档是笔者在阅读《剑指Offer——名企面试管精讲典型编程题》过程所作笔记,内容主要来自于牛客网,CSDN以及牛客网。由于个人对C++不精通,在看书过程中就直接掠过C++代码,查看CSDN、牛客网等资料,参考相关Java、Python代码,在这里感谢那些作者无私地把自己的解题思想以及对题目的解析分享在网上,这也是笔者需要学习的,这里就把自己看题做题的过程记录如下,并使用牛客网中的剑指offer刷题模型进行代码测试。笔者临近找工作时期,但是也想把自己学习的过程以及对题目的总结分享出来,笔记也难免会出现错误,如发现错误,还请读者不吝赐教,给与建议,若有不能看懂,不能理解的读者可以留言,我们共同讨论,学习,进步。

二维数组中的查找 (数组)

题目描述

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

解题思路


二维数组是有序的,从右上角来看,向左数字递减,向下数字递增。因此从右上角开始查找,当然也可以从左下角开始,原理相同。

  • 当要查找数字比右上角数字大时,下移;
  • 当要查找数字比右上角数字小时,左移;
  • 如果出了边界,则说明二维数组中不存在该整数。

参考代码

public class Solution {
        public boolean Find(int target, int[][] array) {
            if (array.length == 0 || array[0].length == 0)
                return false;
            int m = array[0].length - 1; // 获取列数
            int n = 0; // 初始化行数
            int temp = array[n][m]; // 从右上角开始进行比较
            while (target != temp) {
                if (m > 0 && n < array.length - 1) {
                    if (target > temp) n++; // 行加 
                    else m--; // 列减
                    temp = array[n][m];// 更新值
                } else return false;
            }
            return true;
        }
}
class Solution:
    # array 二维数组
    def Find(self, target, array):
        if len(array) == 0 or len(array[0]) == 0: return False
        n,m=0,len(array[0]) -1  # 初始化行列
        temp = array[n][m]      # 获取右上角的数值
        while temp != target:
            if n < len(array) - 1 and m > 0:
                if target > temp:
                    n = n + 1
                else:
                    m = m -1
                temp = array[n][m] # 更新
            else:
                return False
        return True
正文到此结束
本文目录