难度: 中等 | 标签: 查找

1. 题目描述

https://leetcode.cn/problems/search-a-2d-matrix-ii/
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1：
searchgrid2.jpg
输入：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
示例 2：
searchgrid.jpg
输入：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 = 20
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109

通过次数: 269,421 | 提交次数: 527,443

2. 题解

2022-05-10 AC, 一开始想的二分查找, 倒是也能过, 效率不太行
效率的方式是从右上往左下查找

  1. <?php
  2. /**
  3.  * Created by PhpStorm
  4.  * User: jtahstu
  5.  * Time: 2022/5/10 15:36
  6.  * Des: 剑指 Offer 04. 二维数组中的查找
  7.  *      https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
  8.  *      240. 搜索二维矩阵 II
  9.  *      https://leetcode.cn/problems/search-a-2d-matrix-ii/
  10.  *      在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
  11.  */
  13. class Solution
  14. {
  16.     /**
  17.      * @param Integer[][] $matrix
  18.      * @param Integer $target
  19.      * @return Boolean
  20.      */
  21.     function findNumberIn2DArray($matrix, $target)
  22.     {
  23.         if (!$matrix || !count($matrix) || !count($matrix[0])) {
  24.             return false;
  25.         }
  26.         $n = count($matrix);
  27.         $m = count($matrix[0]);
  28.         $i = 0;
  29.         $j = $m - 1;
  30.         while ($i < $n && $j >= 0) {
  31.             $x = $matrix[$i][$j];
  32.             if ($x == $target) {
  33.                 return true;
  34.             } elseif ($x > $target) {  //大于目标值往左
  35.                 $j--;
  36.             } else {  //小于目标值往下
  37.                 $i++;
  38.             }
  39.         }
  40.         return false;
  42.         /**
  43.          * 执行用时：76 ms, 在所有 PHP 提交中击败了5.77%的用户
  44.          * 内存消耗：24.7 MB, 在所有 PHP 提交中击败了69.23%的用户
  45.          * 通过测试用例：129 / 129
  46.          */
  48.         /**
  49.          * 下面自己想的解法, 速度竟然更快? 不敢相信
  50.          * 执行用时：52 ms, 在所有 PHP 提交中击败了53.85%的用户
  51.          * 内存消耗：25.1 MB, 在所有 PHP 提交中击败了5.77%的用户
  52.          * 通过测试用例：129 / 129
  53.          */
  54.     }
  56.     //自己想的, 不算快
  57.     function findNumberIn2DArray2($matrix, $target)
  58.     {
  59.         $n = count($matrix);
  60.         if ($n == 0) {
  61.             return false;
  62.         }
  63.         $m = count($matrix[0]);
  64.         if ($m == 0) {
  65.             return false;
  66.         }
  67.         for ($i = 0; $i < $n; $i++) {
  68.             if ($matrix[$i][0] > $target) {
  69.                 break;
  70.             }
  71.             $matrix[$i] = array_slice($matrix[$i], 0, $m);
  72.             $row = $this->binary_search($matrix[$i], $target);
  73. //            echo $row . PHP_EOL;
  74. //            echo implode(" ", $matrix[$i]) . PHP_EOL;
  75.             if ($row == PHP_INT_MAX) {
  76.                 return true;
  77.             } else {
  78.                 $m = $row;
  79.             }
  80.         }
  81.         return false;
  82.     }
  84.     function binary_search($nums, $target)
  85.     {
  86.         $l = 0;
  87.         $r = count($nums) - 1;
  88.         while ($l <= $r) {
  89.             $mid = intval(($l + $r) / 2);
  90.             $v = $nums[$mid];
  91.             if ($target == $v) {
  92.                 return PHP_INT_MAX;
  93.             }
  94.             if ($v > $target) {
  95.                 $r = $mid - 1;
  96.             }
  97.             if ($v < $target) {
  98.                 $l = $mid + 1;
  99.             }
  100.         }
  101.         return $l;
  102.     }
  103. }
  105. $a = [
  106.     [1, 4, 7, 11, 15],
  107.     [2, 5, 8, 12, 19],
  108.     [3, 6, 9, 16, 22],
  109.     [10, 13, 14, 17, 24],
  110.     [18, 21, 23, 26, 30]
  111. ];
  112. var_dump((new Solution)->findNumberIn2DArray($a, 16));
  113. var_dump((new Solution)->findNumberIn2DArray($a, 20));
  115. /**
  116.  * 执行用时：48 ms, 在所有 PHP 提交中击败了88.16%的用户
  117.  * 内存消耗：24.9 MB, 在所有 PHP 提交中击败了28.95%的用户
  118.  * 通过测试用例：129 / 129
  119.  */
  122. //原来是从右上往左下遍历呀, 没想到没想到
  123. //class Solution {
  124. //    public boolean findNumberIn2DArray(int[][] matrix, int target) {
  125. //        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  126. //            return false;
  127. //        }
  128. //        int rows = matrix.length, columns = matrix[0].length;
  129. //        int row = 0, column = columns - 1;
  130. //        while (row < rows && column >= 0) {
  131. //            int num = matrix[row][column];
  132. //            if (num == target) {
  133. //                return true;
  134. //            } else if (num > target) {
  135. //                column--;
  136. //            } else {
  137. //                row++;
  138. //            }
  139. //        }
  140. //        return false;
  141. //    }
  142. //}