题解

本题要求 高效搜索，最优解法为 "Z 字型查找"，时间复杂度 O(m + n)。

解法：Z 字型查找

核心思路：

• 由于矩阵

  行递增、列递增

  ，我们可以从

  右上角

  （或

  左下角

  ）出发：

  • 如果当前值 matrix[i][j] == target，返回 true。
  • 如果当前值 > target，左移（j--）。
  • 如果当前值 < target，下移（i++）。

• 若超出矩阵边界，则返回 false。

时间复杂度

• 每次比较后移动一步，最多 m + n 步，故 O(m + n)。

代码实现

C++ 实现

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

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int i = 0, j = n - 1; // 从右上角出发

    while (i < m && j >= 0) {
        if (matrix[i][j] == target) return true;
        else if (matrix[i][j] > target) j--; // 向左移动
        else i++; // 向下移动
    }

    return false;
}

int main() {
    int m, n, target;
    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];
        }
    }
    cin >> target;

    cout << (searchMatrix(matrix, target) ? "true" : "false") << endl;
    return 0;
}

Python 实现

def search_matrix(matrix, target):
    """
    Z 字型搜索矩阵
    """
    if not matrix:
        return False

    m, n = len(matrix), len(matrix[0])
    i, j = 0, n - 1  # 从右上角开始

    while i < m and j >= 0:
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] > target:
            j -= 1  # 向左移动
        else:
            i += 1  # 向下移动

    return False

if __name__ == "__main__":
    m, n = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(m)]
    target = int(input())

    print("true" if search_matrix(matrix, target) else "false")

Java 实现

import java.util.Scanner;

public class Main {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n - 1; // 从右上角开始搜索

        while (i < m && j >= 0) {
            if (matrix[i][j] == target) return true;
            else if (matrix[i][j] > target) j--; // 向左移动
            else i++; // 向下移动
        }

        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(), n = scanner.nextInt();
        int[][] matrix = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        int target = scanner.nextInt();
        scanner.close();

        System.out.println(searchMatrix(matrix, target) ? "true" : "false");
    }
}

题目描述

编写一个 高效的算法 来搜索 m × n 矩阵 matrix 中的目标值 target。该矩阵具有以下特性：

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

输入格式

• 第一行输入两个整数 m 和 n，表示矩阵的行数和列数。（1 ≤ m, n ≤ 300）
• 接下来的 m 行，每行输入 n 个整数，表示矩阵的元素。（-10^9 ≤ matrix[i][j] ≤ 10^9）
• 最后一行输入一个整数 target，表示要搜索的目标值。（-10^9 ≤ target ≤ 10^9）

输出格式

• 输出 true 或 false，表示是否在矩阵中找到 target。

输入样例 1

5 5
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
5

输出样例 1

true

输入样例 2

5 5
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
20

输出样例 2

false