LeetCode 74 Search a 2D Matrix

Tag: 二分搜索 LeetCode Posted on 2022-03-26 10:33:59 Edited on 2022-03-26 10:40:55 Views: 149

概述

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

二分搜索

实际上就是把一个排好序的列表给 reshape 成了矩阵,所以做一个 idx 映射就好。

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

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