二维数组中的查找(简单)

01 Jun 2020 1680字 6分次
BY-SA 4.0（除特别声明或转载文章外）

一、题目描述

在一个 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。

限制

<= n <= 1000

<= m <= 1000

二、题目解析

暴力法遍历

对二维数组进行遍历，若找到目标值，则返回true，否则返回false。

 /**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
 var findNumberIn2DArray = function(matrix, target) {
     let targetFound = false;
     if(matrix == null || !matrix.length || !matrix[0].length) return targetFound;
     const columns = matrix[0].length;
     const rows = matrix.length;
     for(let i = 0;i < rows;i ++) {
         for(let j = 0;j < columns;j ++) {
             if(matrix[i][j] === target) {
                 targetFound = true;
                 return targetFound;
             }
         }
     }
     return targetFound;
 };

时间复杂度: O(n^2)
空间复杂度: O(1)

线性遍历法

从矩阵的右上角对矩阵进行遍历，如果target大于遍历到的当前元素，那么行数加1. 如果target小于遍历到的当前元素，那么列数减1，如果target等于遍历到的当前元素，那么终止循环即可。

如何确保这样的遍历方法会遍历到全部元素呢？根据给出矩阵的特点，从左到右是递增的，

从上到下是递增的。我们从矩阵的右上角开始遍历，如果target小于遍历到的当前元素，

那么说明当前元素下方的元素都大于target值，往下遍历不可能找到target值，因此要往

左查找。反之如果target大于遍历到的当前元素，那么说明target大于当前元素左边的全部

元素，往左查找不可能找到target值,因此只能往下查找。
```
 /**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
 var findNumberIn2DArray = function(matrix, target) {
     let targetFound = false;
     if(matrix == null || !matrix.length || !matrix[0].length) return targetFound;
     const columns = matrix[0].length;
     const rows = matrix.length;
     let currentRow = 0, currentColumn = columns - 1;
     while(currentColumn >= 0 && currentRow < rows) {
         if(target > matrix[currentRow][currentColumn]) {
             currentRow ++;
         } else if(target < matrix[currentRow][currentColumn]) {
             currentColumn --;
         } else {
             targetFound = true;
             break;
         }
     }
     return targetFound;
 };
```
- 时间复杂度: O(m+n) (m为行数,n为列数)
- 空间复杂度: O(1)

来源：力扣（LeetCode）

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

二维数组中的查找(简单) yinshibanxian

一、题目描述

二、题目解析