《剑指offer》之二维数组中的查找

程序员爱酸奶

发布于 2020-02-29 17:19:23

33600

代码可运行

文章被收录于专栏：程序员爱酸奶程序员爱酸奶

运行总次数：0

代码可运行

前言

在家呆着没什么事做，今天开始每天刷一道算法题吧。不多不少，重在自己能坚持下去。所有的算法题都是用Java写的，有兴趣的小伙伴可以一起啊。

题目

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

分析

这道题目是一个有序的二维数组，给我们一个数判断这个数是否在二维数组中。这里的重点是判断，而不用对二维数组进行校验，所以这里实现起来其实也比较简单。

解法一

我们完全可以暴力解决，遍历这个二维数组，判断是否在其中。

public boolean Find(int target, int [][] array) {
        if(array==null|| array.length <= 1){
            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 4 2 3 4 6 4 5 7 8

如果目标数小于每行的最后一个数，则目标数可能在这一行，从这一行往前找，如果发现某一个值小于目标值，就从下一行最后一个值开始找。比如上面的例子，需要找5 的话 1、先5和第一行的最后一个值4比较，大于4。i++ 2、5和第二行的6比较，小于6 。j-- 3、5和第二行的4 比较，大于4。i++ 4、5 和第三行的8比较，小于8 。j-- 5、5 和第三行的7比较，小于7 。j-- 6、5 和第三行的5比较，等于5 。返回true

所以代码如下：

public static boolean find(int [][] array,int target) {
        int i=0;
        int j=array[0].length-1;
        int n=array.length;
        while(i<n && j>=0){
            if(target==array[i][j])
                return true;
            else if(target>array[i][j])
                i++;
            else
                j--;
        }
        return false;

    }

源代码

package com.quellanan.algorithm.day1;
import java.util.Scanner;
public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入行数");
        int n=scanner.nextInt();
        System.out.println("请输入列数");
        int m=scanner.nextInt();
        System.out.println("请输入二维数组");
        int[][] array=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                array[i][j]=scanner.nextInt();
                System.out.print(array[i][j]+"\t");
            }
            System.out.println("");
        }
        System.out.println("请输入目标数字");
        int targer=scanner.nextInt();
        System.out.println(find(array,targer));
    }

    public static boolean find(int [][] array,int target) {
        int i=0;
        int j=array[0].length-1;
        int n=array.length;
        while(i<n && j>=0){
            if(target==array[i][j])
                return true;
            else if(target>array[i][j])
                i++;
            else
                j--;
        }
        return false;

    }
}

运行结果

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-02-03，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自程序员爱酸奶微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度