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

剑指offer最优解免费

本问题对应的 leetcode 原文链接：剑指 Offer 04. 二维数组中的查找

问题描述

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

示例 1：

现有矩阵 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

解题思路

视频讲解直达：本题视频讲解

代码实现

       if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
            return false;
        }
        // 这里 cols 表示多少行的意思（但是有人说 cols 是表示列，那我可能记错了）
        int cols = matrix.length;
        // rows 表示多少列的意思
        int rows = matrix[0].length;
        // 左下角的位置
        int col = cols - 1;
        int row = 0;
        // 向上向右走的过程中不能出界
        while(col >= 0 && row < rows){
            if(target > matrix[col][row]){
                row++;
            } else if(target < matrix[col][row]){
                col--;
            } else {
                return true;
            }
        }
        return false;
    }

时间复杂度：O(n+m)
额外空间复杂度：O(1)

Python

class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or len(matrix) <= 0 or len(matrix[0]) <= 0:
            return False
        # 这里 cols 表示多少列的意思（但是有人说 cols 是表示行，那我可能记错了）
        cols = len(matrix)
        # rows 表示多少行的意思
        rows = len(matrix[0])
        # 左下角的位置
        col = cols - 1
        row = 0
        # 向上向右走的过程中不能出界
        while(col >= 0 and row < rows):
            if(target > matrix[col][row]):
                row += 1
            elif(target < matrix[col][row]):
                col -= 1
            else:
                return True
        return False

C++

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()){
            return false;
        }
        // 这里 cols 表示多少列的意思（但是有人说 cols 是表示行，那我可能记错了）
        int cols = matrix.size();
        // rows 表示多少行的意思
        int rows = matrix[0].size();
        // 左下角的位置
        int col = cols - 1;
        int row = 0;
        // 向上向右走的过程中不能出界
        while(col >= 0 && row < rows){
            if(target > matrix[col][row]){
                row++;
            } else if(target < matrix[col][row]){
                col--;
            } else {
                return true;
            }
        }
        return false;
    }
};

Go

func findNumberIn2DArray(matrix [][]int, target int) bool {
    if matrix == nil || len(matrix) <= 0 || len(matrix[0]) <= 0 {
        return false
    }
    // 这里 cols 表示多少列的意思（但是有人说 cols 是表示行，那我可能记错了）
    cols := len(matrix)
    // rows 表示多少行的意思
    rows := len(matrix[0])
    // 左下角的位置
    col := cols - 1
    row := 0
    // 向上向右走的过程中不能出界
    for col >= 0 && row < rows {
        if target > matrix[col][row] {
            row++
        } else if target < matrix[col][row] {
            col--
        } else {
            return true
        }
    }
    return false
}

JS

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function(matrix, target) {
    if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
        return false;
    }
    // 这里 cols 表示多少行的意思（但是有人说 cols 是表示列，那我可能记错了）
    let cols = matrix.length;
    // rows 表示多少列的意思
    let rows = matrix[0].length;
    // 左下角的位置
    let col = cols - 1;
    let row = 0;
    // 向上向右走的过程中不能出界
    while(col >= 0 && row < rows){
        if(target > matrix[col][row]){
            row++;
        } else if(target < matrix[col][row]){
            col--;
        } else {
            return true;
        }
    }
    return false;
};

剑指offer题解