题解 | 二维数组中的查找

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 rows = array.size();
        int cols = array[0].size();

        // 从右上角开始搜索
        int row = 0;
        int col = cols - 1;

        while (row < rows && col >= 0) {
            if (array[row][col] == target) {
                return true;  // 找到目标值
            } else if (array[row][col] > target) {
                col--;  // 当前值太大，向左移动（排除整列）
            } else {
                row++;  // 当前值太小，向下移动（排除整行）
            }
        }

        return false;  // 未找到目标值
    }
};

方法思路
这个问题是在一个特殊的二维数组（矩阵）中查找目标值。该矩阵的每一行从左到右递增，每一列从上到下递增。我们可以利用这种特殊的排序特性来高效地查找目标值。

问题分析：矩阵具有行列递增的特性，这意味着我们可以从矩阵的右上角或左下角开始查找，利用这种特性快速缩小搜索范围。

算法选择：从矩阵的右上角开始查找：
如果当前元素等于目标值，返回true。
果当前元素大于目标值，由于当前列是递增的，目标值不可能在当前列中，因此向左移动一列。
如果当前元素小于目标值，由于当前行是递增的，目标值不可能在当前行中，因此向下移动一行。

复杂度分析：该算法的时间复杂度为O(n + m)，其中n是矩阵的行数，m是矩阵的列数。空间复杂度为O(1)，因为只使用了常数级别的额外空间。

选择右上角或左下角的关键优势：
1.控制变量：每次比较都能确定性地排除一整行或一整列
2.搜索路径唯一：不会出现多方向选择的困境
3.时间复杂度最优：O(n+m)，最多遍历n行+m列
这种选择利用了矩阵的特殊排序性质，将二维搜索问题转化为一维的线性遍历，是典型的"以空间换时间"的优化策略。