搜索二维矩阵

算法思路

题目给定的矩阵满足以下两个条件：

• 每行中整数从左到右非严格递增排列；
• 每行的第一个整数大于上一行最后一个整数。

这两个条件说明整个矩阵可以看作一个有序的一维数组。可以将矩阵的下标映射为一维下标，然后使用二分查找算法快速判断目标值是否存在。具体做法如下：

1. 计算矩阵总元素个数，并用二分查找在区间 [0, m*n-1] 内进行搜索。
2. 通过映射关系：二维下标(row, col) = (index // n, index % n)，将一维下标转换为对应的矩阵位置，比较该位置的数值与 target。
3. 根据比较结果调整二分查找区间，直至找到目标或区间为空。

这种方法的时间复杂度为 O(log(m*n))，空间复杂度为 O(1)。

复杂度分析

• 时间复杂度：O(log(m*n))，二分查找每次将搜索区间折半。
• 空间复杂度：O(1)，只使用了常数级额外空间。

Python 代码

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False
        
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        
        # 二分查找过程
        while left <= right:
            mid = (left + right) // 2
            row = mid // n  # 一维下标映射为二维行下标
            col = mid % n   # 一维下标映射为二维列下标
            mid_value = matrix[row][col]
            if mid_value == target:
                return True
            elif mid_value < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

if __name__ == "__main__":
    import sys
    # 读取输入数据
    data = sys.stdin.read().split()
    if not data:
        exit(0)
    # 第一行包含 m 和 n
    m = int(data[0])
    n = int(data[1])
    matrix = []
    # 接下来 m 行，每行 n 个整数
    index = 2
    for _ in range(m):
        row = []
        for _ in range(n):
            row.append(int(data[index]))
            index += 1
        matrix.append(row)
    # 最后一行是 target
    target = int(data[index])
    
    solution = Solution()
    result = solution.searchMatrix(matrix, target)
    # 根据要求输出 "true" 或 "false"
    print("true" if result else "false")

Java 代码

import java.util.Scanner;

public class Main {
    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }
            int m = matrix.length;
            int n = matrix[0].length;
            int left = 0, right = m * n - 1;
            
            // 二分查找
            while(left <= right) {
                int mid = left + (right - left) / 2;
                int row = mid / n;  // 映射为二维数组行下标
                int col = mid % n;  // 映射为二维数组列下标
                int midValue = matrix[row][col];
                if(midValue == target) {
                    return true;
                } else if(midValue < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return false;
        }
    }
    
    // main函数，用于读取输入和输出结果
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取矩阵的行数 m 和列数 n
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] matrix = new int[m][n];
        // 读取矩阵数据
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        // 读取目标值 target
        int target = sc.nextInt();
        sc.close();
        
        Main main = new Main();
        Solution solution = main.new Solution();
        boolean result = solution.searchMatrix(matrix, target);
        // 输出结果：true 或 false
        System.out.println(result ? "true" : "false");
    }
}

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0, right = m * n - 1;
        
        // 二分查找
        while(left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / n;   // 映射为二维数组行下标
            int col = mid % n;   // 映射为二维数组列下标
            int midValue = matrix[row][col];
            if(midValue == target) {
                return true;
            } else if(midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

int main() {
    int m, n;
    // 读取矩阵的行数 m 和列数 n
    cin >> m >> n;
    vector<vector<int>> matrix(m, vector<int>(n));
    // 读取矩阵数据
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    int target;
    // 读取目标值 target
    cin >> target;
    
    Solution solution;
    bool result = solution.searchMatrix(matrix, target);
    // 输出结果：true 或 false
    cout << (result ? "true" : "false") << endl;
    return 0;
}

Leetcode 64.搜索二维矩阵-原题链接

题目内容

给你一个满足下述两条属性的 $m×n$整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 $target$ ，如果 $target$ 在矩阵中，输出 $true$ ；否则，输出 $false$。

输入描述

第一行包含两个整数 $m$ 和 $n$，分别表示矩阵的行数和列数。

接下来的 $m$ 行，每行包含 $n$ 个整数，表示矩阵的元素。

最后一行包含一个整数 $target$。

输出描述

如果 $target$ 存在于矩阵中，则输出 true，否则输出 false。输出不用考虑大小写。

样例1

输入

3 4
1 3 5 7
10 11 16 20
23 30 34 60
3

输出

true

样例2

输入

3 4
1 3 5 7
10 11 16 20
23 30 34 60
13

输出

false

提示

• $m == matrix.length$
• $n == matrix[i].length$
• $1 <= m, n <= 100$
• $-10^4 <= matrix[i][j], target <= 10^4$