搜索二维矩阵 II

题目要求

设计一个高效的算法，用于在一个 m 行 n 列的矩阵中搜索指定的目标值 target。这个矩阵具备以下性质：

每一行的元素都是从左到右递增排序。
每一列的元素都是从上到下递增排序。

解题思路

由于矩阵的行和列都是排序的，我们可以利用这个性质来减少搜索空间。以下是解题的步骤：

从矩阵的右上角开始搜索。设当前位置的元素为 element。
比较 element 和目标值 target：
- 如果 element 等于 target，那么我们找到了目标值，算法结束。
- 如果 element 大于 target，由于 element 是所在列的最小值，所以 target 不可能在当前列中，向左移动一列。
- 如果 element 小于 target，由于 element 是所在行的最大值，所以 target 不可能在当前行中，向下移动一行。
重复步骤 2，直到找到目标值或者搜索范围为空。

这个算法的效率之所以高，是因为每一次比较都排除了一行或者一列的可能性，这样可以以线性时间复杂度（O(m+n)）完成搜索。

Golang 版本

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    // 从右上角开始
    row := 0
    col := len(matrix[0]) - 1

    // 当前位置在矩阵内时循环
    for row < len(matrix) && col >= 0 {
        if matrix[row][col] == target {
            // 找到目标值
            return true
        } else if matrix[row][col] > target {
            // 当前值大于目标值，排除当前列
            col--
        } else {
            // 当前值小于目标值，排除当前行
            row++
        }
    }

    // 没有找到目标值
    return false
}

这段代码实现了上述的解题思路，通过从矩阵的右上角开始，根据当前元素与目标值的比较结果来移动搜索位置，直到找到目标值或者确定目标值不存在于矩阵中。

C++版本

#include <vector>

bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) {
        return false;
    }

    int m = matrix.size();
    int n = matrix[0].size();
    int row = 0;
    int col = n - 1;

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

    return false;
}

这段 C++代码遵循了之前描述的算法逻辑，从矩阵的右上角开始搜索，根据当前元素与目标值的比较结果来决定是向左移动还是向下移动，直到找到目标值或者遍历完矩阵。

Python 版本

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    # 从右上角开始
    row, col = 0, len(matrix[0]) - 1

    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1

    return False

这段 Python 代码实现了之前描述的算法思路，从矩阵的右上角开始搜索，根据当前元素与目标值的比较结果来移动搜索位置，直到找到目标值或者确定目标值不存在于矩阵中。

Java 版本

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = 0;
        int col = matrix[0].length - 1;

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

        return false;
    }
}

这段 Java 代码遵循了之前描述的算法逻辑，从矩阵的右上角开始搜索，根据当前元素与目标值的比较结果来决定是向左移动还是向下移动，直到找到目标值或者遍历完矩阵。

Rust 版本

#![allow(unused)]
fn main() {
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    if matrix.is_empty() || matrix[0].is_empty() {
        return false;
    }

    let (mut row, mut col) = (0, matrix[0].len() as i32 - 1);

    while row < matrix.len() as i32 && col >= 0 {
        match matrix[row as usize][col as usize].cmp(&target) {
            std::cmp::Ordering::Equal => return true,
            std::cmp::Ordering::Greater => col -= 1,
            std::cmp::Ordering::Less => row += 1,
        }
    }

    false
}
}

这段 Rust 代码实现了之前描述的算法思路，从矩阵的右上角开始搜索，根据当前元素与目标值的比较结果来移动搜索位置，直到找到目标值或者确定目标值不存在于矩阵中。在 Rust 中，我们使用cmp方法来比较值，并根据比较结果来控制搜索的方向。

总结

上述解法针对一个特定的矩阵搜索问题，其中矩阵具有每行从左到右递增以及每列从上到下递增的特性。解法的核心思想是利用矩阵的这些性质来减少搜索空间，从而提高搜索效率。

算法从矩阵的右上角开始搜索，根据当前元素与目标值的比较结果来决定搜索的方向：

如果当前元素等于目标值，则搜索成功，返回true。
如果当前元素大于目标值，说明目标值不可能出现在当前元素的列中，因此向左移动一列。
如果当前元素小于目标值，说明目标值不可能出现在当前元素的行中，因此向下移动一行。

这个过程会一直重复，直到找到目标值或者搜索范围为空（即搜索到了矩阵的左下角仍未找到目标值），这时返回false。

这种方法的时间复杂度为 O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数。这是因为在最坏的情况下，算法可能需要遍历矩阵的全部行或全部列。

不同编程语言的实现（Go, C++, Python, Java, Rust）都遵循了这一核心算法思想，只是在语法和一些细节上有所不同。这种解法是对于这类特定矩阵搜索问题的一个高效解决方案。

hot-100