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

前言

在家呆着没什么是做，做今天开始每天刷一道算法题吧。不多不少，重在自己能坚持下去。所有的算法题都是用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;
    }
}