剑指offer:二维数组中的查找 (java版)

2021/7/31 14:06:18

本文主要是介绍剑指offer:二维数组中的查找 (java版),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

描述

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

[

  [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

解题思路

知识复习:

二维数组可以看做是一个特殊的一维数组。

怎么特殊呢,就相当于每一个元素都是一个一维数组。可以参照下图发挥想象力

所以,array[0].length代表列数。

          array.length代表行数。

下面开始我的分析:

法一:当然了,最简单的方法就是暴力遍历,如果找到了,直接return

           脑子不太转想不出来方法的小菜鸟,就最喜欢这种方法啦~(比如我。。。)

代码

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length==0 || array==null){
            return false;
        }
        for(int i=0; i < array.length; i++){
            for(int j=0; j<array[0].length;j++){
                if(array[i][j]==target){
                    return true;
                }
            }
        }
       return false; 
    }
}

法二:大家可以看我标黄色的半圈:

           从左到右,就是从小到大;

           右上角的数字就是标黄部分的中位数。

         

          所以可以变相的采用二分思想

步骤1:从右上角开始,首先选右上角的数字,如果它等于要查找的数字,则查找过程结束。

步骤2:如果要查找的数字大于右上角数字,删除右上角数字所在行,因为要查找的数字在右上角数字所在列

步骤3:如果要查找的数字小于右上角的数字,删除右上角数字所在列,以为要查找的数字在右上角数字所在行

代码

public class Solution {
    public boolean Find(int target, int[][] array) {
        if(array == null || array.length == 0 || array[0].length==0){
            return false;
        }
        int is = array.length;
        int js = array[0].length;

        //从右上角的数字开始 
        int i = 0;
        int j = js - 1;

        while(i <is && j >= 0){
            if(array[i][j] == target){
                return true;
            }else if(array[i][j] > target){
                j--;
            }else{
                i++;
            }
        }
          return false; //矩阵遍历完没有找到,返回false
    }
}

 还有其他方法欢迎补充,我的小脑瓜最喜欢这两种方法啦嘿嘿~

 



这篇关于剑指offer:二维数组中的查找 (java版)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程