LeetCode 240 Search a 2D Matrix II

Tag: 二分搜索 LeetCode Posted on 2022-03-06 11:06:03 Edited on 2022-03-06 11:15:37 Views: 145

概述

https://leetcode.com/problems/search-a-2d-matrix-ii/

二分搜索

我原本想的是,首先用二分搜索找到所在列,再用二分搜索搜索该列。

这种想法是错误的,

我们应当进行二维的二分搜索。

实现的时候注意:

  1. 首先,行是一级索引,列是二级索引,别搞错了;
  2. 其次,当遇到左边界和上边界无法继续更新时,我们需要搜索两条线(外加一个点),而非单纯的一个 2x2 方格

可以了,这种想法依然是错的。我们每次缩小范围时,其实根本不能确定目标值是否在那个方框内。

7 连 WA 和 RE,够了,就这样吧

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int l = 0, r = matrix[0].size() - 1;
        int t = 0, b = matrix.size() - 1;
        while (l <= r && t <= b) {
            int m1 = (t + b) / 2;
            int m2 = (l + r) / 2;
            // cout << m1 << " " << m2 << endl;
            if (m1 == t && m2 == l) {
                // cout << "bingo " << m1 << " " << m2 << endl;
                for (int row = m1, col = m2; col < matrix[0].size(); col ++) {
                    if (matrix[row][col] == target) return true;
                    if (matrix[row][col] > target) break;
                }
                for (int row = m1, col = m2; row < matrix.size(); row ++) {
                    if (matrix[row][col] == target) return true;
                    if (matrix[row][col] > target) break;
                }
                if (m1 + 1 < matrix.size() && m2 + 1 < matrix[0].size()) {
                    if (matrix[m1+1][m2+1] == target) return true;
                }
                return false;
            }
            
            if (matrix[m1][m2] == target) {
                return true;
            } else if (matrix[m1][m2] > target) {
                r = m2;
                b = m1;
            } else {
                l = m2;
                t = m1;
            }
        }
        return false;
    }
};

从右上角开始搜索

https://leetcode.com/problems/search-a-2d-matrix-ii/discuss/66139/C%2B%2B-search-from-top-right

因为从右上角搜索,每次:

  1. 我们要么找到目标值,
  2. 要么可以排除该列,
  3. 要么可以排除该行,

时间复杂度 O(m+n)。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int r = 0, c = matrix[0].size() - 1;
        while (r < matrix.size() && c >= 0) {
            if (matrix[r][c] == target) {
                return true;
            } else if (matrix[r][c] > target) {
                c --;
            } else {
                r ++;
            }
        }
        return false;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/