题目地址(04. 二维数组中的查找)

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

题目描述

  1. 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
  5. 示例:
  7. 现有矩阵 matrix 如下：
  9. [
  10.   [1,   4,  7, 11, 15],
  11.   [2,   5,  8, 12, 19],
  12.   [3,   6,  9, 16, 22],
  13.   [10, 13, 14, 17, 24],
  14.   [18, 21, 23, 26, 30]
  15. ]
  18. 给定 target = 5，返回 true。
  20. 给定 target = 20，返回 false。
  24. 限制：
  26. 0 <= n <= 1000
  28. 0 <= m <= 1000
  32. 注意：本题与主站 240 题相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

前置知识


公司

  • 暂无

思路

暴力法可能面试不让过
把右上角的点看成二叉树的根节点左边小于这个数 下面大于这个数

关键点


代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         public boolean findNumberIn2DArray(int[][] matrix, int target) {
  3.             for (int i = 0; i < matrix.length; i++) {
  4.                 for (int j = 0; j < matrix[i].length; j++) {
  5.                     if (matrix[i][j] == target) {
  6.                         return true;
  7.                     }
  8.                 }
  9.             }
  10.             return false;
  11.         }
  12.     }

  • 时间复杂度：剑指 Offer 04. 二维数组中的查找 - 图1

    1. class Solution {
    2.       public boolean findNumberIn2DArray(int[][] matrix, int target) {
    3.           if(matrix == null || matrix.length == 0) {
    4.           return false;
    5.       }
    6.           int column = matrix[0].length-1;
    7.           int row = 0;
    8.           while (column >= 0 && row < matrix.length) {
    9.               if (matrix[row][column] > target) {
    10.                   column--;
    11.               } else if (matrix[row][column] < target) {
    12.                   row++;
    13.               } else {
    14.                   return true;
    15.               } 
    16.           }
    17.           return false;
    18.       }
    19.   }

  • 时间复杂度：剑指 Offer 04. 二维数组中的查找 - 图2

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 04. 二维数组中的查找 - 图3#card=math&code=O%28n%29&id=RCnl2)
  • 空间复杂度：剑指 Offer 04. 二维数组中的查找 - 图4#card=math&code=O%28n%29&id=mJDtQ)