package com.striner.java.jzOffer;

public class FindNumberIn2DArray04 {

//剑指 Offer 04. 二维数组中的查找

//在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

//

//

//

//示例:

//

//现有矩阵 matrix 如下：

//

//[

// [1, 4, 7, 11, 15],

// [2, 5, 8, 12, 19],

// [3, 6, 9, 16, 22],

// [10, 13, 14, 17, 24],

// [18, 21, 23, 26, 30]

//]

//给定 target = 5，返回 true。

//

//给定 target = 20，返回 false。

//

//

//

//限制：

//

//0 <= n <= 1000

//

//0 <= m <= 1000

//

//https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

public static void main(String[] args) {

// int[][] matrix = new int[][]{{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};

// int[][] matrix = new int[][]{{1, 1}};

int[][] matrix = new int[0][0];

FindNumberIn2DArray04 findNumberIn2DArray04 = new FindNumberIn2DArray04();

System.out.println(findNumberIn2DArray04.findNumberIn2DArray(matrix, 0));

}

public boolean findNumberIn2DArray(int[][] matrix, int target) {

if (0 == matrix.length || 0 == matrix[0].length) return false;

int[][] flagArray = new int[matrix.length][matrix[0].length];

return findNumberIn2DArray(matrix, target, 0, 0, flagArray);

}

public boolean findNumberIn2DArray(int[][] matrix, int target, int i, int j, int[][] flagArray) {

if (i >= matrix.length || j >= matrix[0].length || flagArray[i][j] == 1) return false;

flagArray[i][j] = 1;

if (matrix[i][j] == target) return true;

if (matrix[i][j] < target) return findNumberIn2DArray(matrix, target, i+1, j, flagArray) || findNumberIn2DArray(matrix, target, i, j+1, flagArray);

return false;

}

}

//执行结果： 通过

//执行用时： 1 ms , 在所有 Java 提交中击败了 100.00% 的用户

//内存消耗： 44 MB , 在所有 Java 提交中击败了 77.14% 的用户