1. 首页
  2. 剑指offer经典面试题

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

[剑指 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 上岛屿的问题,特别之处:从右上角开始找,或者从左下角开始找,为什么不能选左上或者右下开始,因为不能缩小查找范围。首先选取数组中右上角的数字。如果该数字等于要查找的数字,查找过程结束;如果该数字大于要查找的数组,剔除这个数字所在的列;如果该数字小于要查找的数字,剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角,则每一次都在数组的查找范围中剔除一行或者一列,这样每一步都可以缩小查找的范围,直到找到要查找的数字,或者查找范围为空。 liwei20191015_1.png

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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3253.html

« [剑指 Offer 第 2 版第 3 题] “数组中重复的数字”做题记录
[剑指 Offer 第 2 版第 5 题] “替换空格”做题记录»

相关推荐

QR code