题解 | 二维数组中的查找

1、解题思路

• 初始化行指针 row = 0 和列指针 col = n - 1（即右上角）。
• 循环直到 row < m 且 col >= 0 ： 如果 array[row][col] == target，返回 true。如果 array[row][col] > target，则目标可能在左侧列，col--。如果 array[row][col] < target，则目标可能在下方行，row++。
• 若循环结束仍未找到，返回 false。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param array int整型vector<vector<>>
     * @return bool布尔型
     */
    bool Find(int target, vector<vector<int> >& array) {
        // write code here
        if (array.empty() || array[0].empty()) {
            return false;
        }
        int m = array.size();
        int n = array[0].size();
        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            if (array[row][col] == target) {
                return true;
            } else if (array[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }

        return false;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param array int整型二维数组
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        // write code here
        if (array == null || array.length == 0 || array[0].length == 0) return false;
        int m = array.length;
        int n = array[0].length;
        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            if (array[row][col] == target) {
                return true;
            } else if (array[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }

        return false;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param array int整型二维数组 
# @return bool布尔型
#
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        if not array or not array[0]:
            return False
        m, n = len(array), len(array[0])
        row, col = 0, n - 1
        
        while row < m and col >= 0:
            if array[row][col] == target:
                return True
            elif array[row][col] > target:
                col -= 1
            else:
                row += 1
        
        return False

3、复杂度分析

• 最坏情况下从右上角移动到左下角，最多移动 m + n 次，时间复杂度为 O(m + n)。
• 空间复杂度为 O(1)，仅使用常数个指针变量。