剑指Offer-Javascript版-二维数组中的查找

对应LeetCode上的题目：面试题04. 二维数组中的查找

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

题目描述

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

解法一，暴力求解法

因为是 n * m 的二维数组，所以我们可以直接使用双层遍历来遍历整个二维数组的项。注意，该方法不管你数组是递增还是递减的规律，直接一梭子遍历就完事了


var findNumberIn2DArray = function(matrix, target) {
    // 多少行
    const rowLength = matrix.length

    if(!rowLength) return false

    // 多少列
    const colLength = matrix[0].length

    if(!colLength) return false

    for(let i = 0; i < rowLength; i++) {
        for(let j = 0; j < colLength; j++) {
            if(matrix[i][j] === target) {
                return true
            }
        }
    }

    return false
};

当然，我们也可以使用数组提供的 API 去解决这道问题，例如：indexOf，includes，但是由于该种做法过于简单，我们刷题的时候应该尽量避免使用此类 API，下面讲述一下思路：

遍历数组的每一个项，再使用数组的每一项去判断子数组中是否存在目标元素（indexOf 判断子数组中目标元素的位置，可以用是否大于 -1 来判断，includes 则是判断数组中是否存在某元素，存在则返回 true，否则返回 false）

解法二，发现规律

从题目描述中可以发现二维数组中的每一行都按照从左到右递增，每一列都按照从上到下递增。我们可以利用这一规律作为解题的突破口，那么

从数组中选取一个数组，分三种情况来分析查找的过程
如果数组中选取的数字刚好等于目标元素，那么直接返回 true，结束查找。
如果选取的数字小于目标元素，那么目标元素的位置应该在选取的数字的右边或者下边
同样，如果选取的数字大于目标元素，那么目标元素的位置应该在选取的数字的左边或者上边


var findNumberIn2DArray = function(matrix, target) {
    const rowLength = matrix.length
    if(!rowLength) {
        return false
    }

    const colLength = matrix[0].length
    if(!colLength) {
        return false
    }

    let row = 0, col = colLength - 1;

    while(row < rowLength && col >= 0) {
        if(matrix[row][col] === target) {
            // 第一种情况
            return true
        } else if(matrix[row][col] > target) {
            // 第三种情况
            --col
        } else {
            // 第二种情况
            ++row
        }
    }

    return false
};

# 数组

剑指Offer-Javascript版-二维数组中的查找

题目描述

解法一，暴力求解法

解法二，发现规律

喜欢这篇文章？打赏一下作者吧

标签云

最新文章

链接

分类

归档

标签

链接

分类

归档

标签

Your browser is out-of-date!