二分查找：二维数组

0074. 搜索二维矩阵 (opens new window)

题目

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

解析

我们可以想象把整个矩阵，按行展开成一个一维数组，那么这个一维数组单调递增，然后直接二分即可。

二分时可以通过整除和取模运算得到二维数组的坐标。

二分算法，见 算法模板：整数二分。

代码

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

0240. 搜索二维矩阵 II (opens new window)

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

解析

本题可从右上角开始遍历，当需要更小的值时向左移动，需要更大的值时向下移动，以此进行二分即可。

代码

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

0302. 包含全部黑色像素的最小矩形 (opens new window)

题目

图片在计算机处理中往往是使用二维矩阵来表示的。

假设，这里我们用的是一张黑白的图片，那么 0 代表白色像素，1 代表黑色像素。

其中黑色的像素他们相互连接，也就是说，图片中只会有一片连在一块儿的黑色像素（像素点是水平或竖直方向连接的）。

那么，给出某一个黑色像素点 (x, y) 的位置，你是否可以找出包含全部黑色像素的最小矩形（与坐标轴对齐）的面积呢？

解析

套用二分法寻找左右边界的模板，调用四次确定矩形的左右和上下边界即可。

代码

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int row = image.size();
        int col = image[0].size();

        int left = searchLeft(image, 0, y, true);
        int right = searchRight(image, y, col - 1, true);

        int top = searchLeft(image, 0, x, false);
        int bottom = searchRight(image, x, row - 1, false);

        return (right - left + 1) * (bottom - top + 1);
    }

    int searchLeft(vector<vector<char>>& image, int left, int right, bool isHor) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (hasBlack(image, mid, isHor)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    int searchRight(vector<vector<char>>& image, int left, int right, bool isHor) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (hasBlack(image, mid, isHor)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    bool hasBlack(vector<vector<char>>& image, int x, bool isHor) {
        if (isHor) {
            for (int i = 0; i < image.size(); i ++) {
                if (image[i][x] == '1') return true;
            }
        } else {
            for (int j = 0; j < image[0].size(); j ++) {
                if (image[x][j] == '1') return true;
            }
        }
        return false;
    }
};

0378. 有序矩阵中第 K 小的元素 (opens new window)

题目

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

解析

值域二分，根据题意可知矩阵从左上角到右下角为递增序列，可通过统计不超过中值的元素数量来进行二分，当 left 和 right 的值相等时即找到目标值。

代码

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + (right - left) / 2;
            int num = notBiggerCount(matrix, mid);
            if (num < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }

    int notBiggerCount(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int ans = 0;
        int i = n - 1, j = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= target) {
                ans += i + 1;
                j ++;
            } else i --;
        }
        return ans;
    }
};

0419. 甲板上的战舰 (opens new window)

题目

给定一个二维的甲板， 请计算其中有多少艘战舰。 战舰用 'X'表示，空位用 '.'表示。 你需要遵守以下规则：

• 给你一个有效的甲板，仅由战舰或者空位组成。
• 战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。
• 两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。

解析

遍历整个数组，若 X 的上方和左方都不为 X 则结果加一。

代码

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int ans = 0;
        for (int i = 0; i < board.size(); i ++) {
            for (int j = 0; j < board[0].size(); j ++) {
                if (board[i][j] == '.') continue;
                if (i > 0 && board[i - 1][j] == 'X') continue;
                if (j > 0 && board[i][j - 1] == 'X') continue;
                ans ++;
            }
        }
        return ans;
    }
};