0074. 搜索二维矩阵 Search a 2D Matrix

问题描述

这个题目适合使用二分查找法. 但在解题之外, 我们先试试暴力法.

暴力法

把所有的元素拷贝一遍到新的数组中, 然后使用二分查找法:

#![allow(unused)]
fn main() {
// Brute force
pub fn search_matrix1(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let items = matrix.len() * matrix[0].len();
    let mut nums = Vec::with_capacity(items);
    for row in matrix {
        nums.extend(row);
    }

    nums.binary_search(&target).is_ok()
}
}

真正运行时, 这个方法其实并不算太慢. 时间复杂度是 O(m n), 空间复杂度是 O(m n).

二分查找法

考虑题目中的条件:

• 每行数据是递增的
• 每列数据也是递增的

根据上面的条件, 我们的解决思路是:

1. 先使用二分查找法遍列第一列, 找到 target 可能位于哪一行
2. 然后再利用二分查找法遍历该行, 确定 target 是否存在于当前行

但要注意一下细节:

1. 在查找行时, 我们使用 while top < bottom 的条件判断, 该循环终止的条件是 left == right
2. 而且计算 middle 值时, 使用的是 let middle = left + (right - left + 1) / 2, 这样的话, 中间值会偏下一位, 但因为之后的条件, bottom = middle - 1, 这样才不会进行死循环
3. 在查找行数据时, 我们使用 while left <= right 的条件, 该循环的终止条件是, 找到了 target, 或者 left > right 没有找到

代码实现如下:

#![allow(unused)]
fn main() {
// Binary Search
pub fn search_matrix2(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    // 两次二分查找:
    // 1. 确定 target 应该属于哪个行
    // 2. 确定 target 是否在当前行

    debug_assert!(!matrix.is_empty() && !matrix[0].is_empty());

    // 极端情况.
    let last_row = matrix.len() - 1;
    let last_col = matrix[0].len() - 1;
    if target < matrix[0][0] || target > matrix[last_row][last_col] {
        return false;
    }

    let mut top = 0;
    let mut bottom = last_row;
    // 循环终止条件是 top == bottom
    while top < bottom {
        let middle = top + (bottom - top + 1) / 2;
        if matrix[middle][0] > target {
            // target 位于 middle 上面的行
            bottom = middle - 1;
        } else {
            top = middle;
        }
    }
    debug_assert!(top == bottom);
    debug_assert!(matrix[top][0] <= target);
    if top < last_row {
        debug_assert!(target <= matrix[top + 1][0]);
    }

    let mut left = 0;
    let mut right = last_col;
    let row = &matrix[top];
    while left <= right {
        let middle = left + (right - left) / 2;
        match row[middle].cmp(&target) {
            Ordering::Equal => return true,
            Ordering::Less => left = middle + 1,
            Ordering::Greater => right = middle.saturating_sub(1),
        }
    }

    false
}
}

算法的时间复杂度是 O(log(m n)), 空间复杂度是 O(1).