数组-剑指offer3数组中重复的数字-中等-20210807

1. 题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个==高效的函数==，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。
给定 target = 20，返回 false。

2. 题目解答

2.1 第一次尝试答案-暴力解法

时间复杂度：O(nm)

空间复杂度：O(1)

思路：

• ① 不考虑二维数组排好序的特点，则直接遍历整个二维数组的每一个元素，判断目标值是否在二维数组中存在。

• ① 依次遍历二维数组的每一行和每一列。如果找到一个元素等于目标值，则返回 true。如果遍历完毕仍未找到等于目标值的元素，则返回 false。

class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        # 应考虑特殊情况
        if not matrix or len(matrix)==0 or len(matrix[0])==0 :
            return False
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == target:
                    return True
        return False # bug：返回false应该在判断完所有之后的循环之外

2.2 参考解法(较优)

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

空间复杂度：O(1)

思路：利用已排序的特征

从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。

如果当前元素大于目标值，则移到左边一列（当前元素的下边的所有元素都一定大于目标值）；如果当前元素小于目标值，则移到下边一行（说明当前元素的左边的所有元素都一定小于目标值）。

• ① 若数组为空，返回 false

• ② 初始化行下标为 0，列下标为二维数组的列数减 1

• ③ 重复下列步骤，直到行下标或列下标超出边界

  ​ 获得当前下标位置的元素 num

  • 如果 num 和 target 相等，返回 true

  • 如果 num 大于 target，列下标减 1

  • 如果 num 小于 target，行下标加 1

    循环体执行完毕仍未找到元素等于 target ，说明不存在这样的元素，返回 false`

class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
        '''
        从右上角
        :param matrix: int
        :param target: int
        :return: bool
        '''
        #  illegal input
        if not matrix or len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        #  find target num
        row, column = 0, len(matrix[0])-1
        while row < len(matrix) and column >= 0:
            if matrix[row][column] == target:
                return True
            elif matrix[row][column] > target:
                column -= 1
            else:
                row += 1
        return False

    def findLeft(self, matrix, target):
        '''
        从左下角开始找
        :param matrix: 
        :param target: 
        :return: 
        '''
        if not matrix or len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        row, column = len(matrix)-1, 0
        while column < len(matrix[0]) and row >= 0:
            if matrix[row][column] == target:
                return True
            elif matrix[row][column] > target:
                row -= 1
            else:
                column +=  1
        return False


if __name__ == '__main__':
    matrix1 = [[]]
    matrix2 = [
        [1, 2, 8, 9],
        [2, 4, 9, 12],
        [4, 7, 10, 13],
        [6, 8, 11,15]
    ]

    # Test case
    Solution = Solution()
    print(Solution.findNumberIn2DArray(matrix1, 7))
    print(Solution.findNumberIn2DArray(matrix2, 7))
    print(Solution.findNumberIn2DArray(matrix2, 15))
    print(Solution.findNumberIn2DArray(matrix2, 1))
    print(Solution.findNumberIn2DArray(matrix2, 20))
    print(Solution.findNumberIn2DArray(matrix2, 0))
    print(Solution.findNumberIn2DArray(matrix2, 3))

    print(Solution.findLeft(matrix1, 7))
    print(Solution.findLeft(matrix2, 7))
    print(Solution.findLeft(matrix2, 15))
    print(Solution.findLeft(matrix2, 1))
    print(Solution.findLeft(matrix2, 20))
    print(Solution.findLeft(matrix2, 0))
    print(Solution.findLeft(matrix2, 3))

3. 测试用例

1. 空数组
2. 二维数组中包含查找的数字（查找的数字是数组中的最大值/最小值/中间值）
3. 二维数组不包含查找的数字（大于/小于/处于中间但没有该值）