[剑指 Offer 第 2 版第 4 题] “二维数组中的查找”做题记录

第 4 题：二维数组中的查找

同 LeetCode 第 240 题，LeetCode 传送门：搜索二维矩阵 II，AcWing：二维数组中的查找，牛客网传送门：二维数组中的查找。

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例：

输入数组：

[ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ]

如果输入查找数值为 7，则返回 true，

如果输入查找数值为 5 ，则返回 false。

分析：有点像 LeetCode 上岛屿的问题，特别之处：从右上角开始找，或者从左下角开始找，为什么不能选左上或者右下开始，因为不能缩小查找范围。首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

Python 代码：从右上角开始找，一个一个地找。小了向下面走，大了向左边走

  class Solution(object):

        def searchArray(self, array, target):
            rows = len(array)
            if rows == 0:
                return False

            cols = len(array[0])
            if rows > 0 and cols > 0:
                row = 0
                col = cols - 1
                # 注意：在横纵坐标都有意义的时候，才可以搜索，因此用 and
                while row < rows and col >= 0:
                    if target == array[row][col]:
                        return True
                    elif target < array[row][col]:
                        # [4, 5, 6, 12, 13] 找 7
                        col -= 1
                    else:
                        # [7]
                        # [8]
                        # [12] 找 9
                        row += 1
            # 全部走完都找不到，就说明没有
            return False

说明：其实不管是每行还是每列，都是有序数组，所以可以使用二分法。我写了个二分法，只是作为练习。但是二分法不能保证一次写对，所以不建议在面试的时候写。

• 正确的搜索起点是从左下角或者右上角开始搜索，这是因为： 从下到上，数字越来越小；
  从左到右，数字越来越大。
• 注意指针没有必要回退，这一点，在下面的代码注释中做了强调。

Java 代码：

  public class Solution {

        public boolean Find(int target, int[][] array) {
            int row = array.length;
            if (row == 0) {
                return false;
            }
            int col = array[0].length;
            // 从左下角开始搜索，先从左到右，再从下到上
            int i = row - 1;

            int j = 0;
            while (i >= 0) {
                while (j < col && array[i][j] < target) {
                    j++;
                }
                if (j < col && array[i][j] == target) {
                    return true;
                }
                i--;
            }
            return false;
        }

        public static void main(String[] args) {
            int[][] matrix = new int[][]{
                    {1, 2, 8, 9},
                    {2, 4, 9, 12},
                    {4, 7, 10, 13},
                    {6, 8, 11, 15}
            };
            Solution solution = new Solution();
            boolean find = solution.Find(16, matrix);
            System.out.println(find);
        }
    }

Python 代码：（了解即可）

  # 4、二维数组中的查找

    class Solution(object):

        # 二分法查找规律
        # 1、从右到左，找第 1 个小于或者等于 target 的数
        # 2、从上到下，找第 1 个大于或者等于 target 的数

        def searchArray(self, array, target):
            """
            :type array: List[List[int]]
            :type target: int
            :rtype: bool
            """

            rows = len(array)
            if rows == 0:
                return False
            cols = len(array[0])

            col = cols - 1
            row = 0

            while row < rows and col >= 0:

                # print('row', row, 'col', col, array[row][0])
                # 1、从右到左，找第 1 个小于或者等于 target 的数
                if col == 0 and array[row][0] > target:
                    return False
                l = 0
                r = col
                while l < r:
                    mid = l + (r - l + 1) // 2
                    if array[row][mid] <= target:
                        l = mid
                    else:
                        assert array[row][mid] > target
                        r = mid - 1
                col = l

                # 2、从上到下，找第 1 个大于或者等于 target 的数
                if row == rows - 1 and array[rows - 1][col] < target:
                    return False

                l = row
                r = rows - 1
                while l < r:
                    mid = l + (r - l) // 2
                    if array[mid][col] >= target:
                        r = mid
                    else:
                        assert array[mid][col] < target
                        l = mid + 1
                row = l

                if array[row][col] == target:
                    return True

            return False


    if __name__ == '__main__':
        array = [[1, 2, 8, 9],
                 [2, 4, 9, 12],
                 [4, 7, 10, 13],
                 [6, 8, 11, 15]]
        target = 16
        solution = Solution()
        result = solution.searchArray(array, target)
        print(result)

LeetCode 第 74 题：搜索二维矩阵

传送门：搜索二维矩阵。

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

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

示例 1:

输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true

示例 2:

输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false

Python 代码1：“标准的”二分法

  class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            m = len(matrix)
            if m == 0:
                return False
            n = len(matrix[0])
            if n == 0:
                return False
            left = 0
            # 这里一定要记得减 1
            right = m * n - 1
            while left <= right:
                mid = left + (right - left) // 2
                # 定位到矩阵中
                num = matrix[mid // n][mid % n]
                if num == target:
                    return True
                elif num < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return False

Python 代码2：“神奇的”二分法模板

  class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            m = len(matrix)
            if m == 0:
                return False
            n = len(matrix[0])
            # [[]] 针对这种情况，要特判
            if n == 0:
                return False

            l = 0
            r = m * n - 1

            while l < r:
                mid = l + (r - l) // 2
                if matrix[mid // n][mid % n] < target:
                    l = mid + 1
                else:
                    r = mid
            # 这个模板在退出循环的时候 l == r 成立，但是有可能存在不满足条件的时候
            # 所以要单独判断
            return matrix[l // n][l % n] == target

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/