解题思路

这是一道在有序矩阵中查找数字的题目，主要思路如下：

  1. 问题特点：

    • 矩阵每行从小到大排序
    • 矩阵每列从小到大排序
    • 需要查找目标数字 是否存在

  2. 解决方案：

    • 从矩阵右上角开始查找
    • 如果当前数字大于目标值，向左移动
    • 如果当前数字小于目标值，向下移动
    • 直到找到目标值或超出边界

代码

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

int main() {
    int 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;
    cin >> target;
    
    // 从右上角开始查找
    int row = 0;
    int col = n - 1;
    bool found = false;
    
    while(row < m && col >= 0) {
        if(matrix[row][col] == target) {
            found = true;
            break;
        } else if(matrix[row][col] > target) {
            col--;
        } else {
            row++;
        }
    }
    
    cout << (found ? "true" : "false") << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        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();
            }
        }
        
        int target = sc.nextInt();
        
        // 从右上角开始查找
        int row = 0;
        int col = n - 1;
        boolean found = false;
        
        while(row < m && col >= 0) {
            if(matrix[row][col] == target) {
                found = true;
                break;
            } else if(matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        
        System.out.println(found ? "true" : "false");
    }
}

def main():
    # 读入矩阵大小
    m, n = map(int, input().split())
    
    # 读入矩阵
    matrix = []
    for _ in range(m):
        row = list(map(int, input().split()))
        matrix.append(row)
    
    target = int(input())
    
    # 从右上角开始查找
    row, col = 0, n - 1
    found = False
    
    while row < m and col >= 0:
        if matrix[row][col] == target:
            found = True
            break
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    
    print("true" if found else "false")

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：线性查找
  • 时间复杂度： - 最多需要移动 次
  • 空间复杂度： - 只需要常数级别的额外空间