剑指 Offer 2022/6/29

剑指 Offer 03. 数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

代码思路：

1. 数组遍历
   这就是最简单的寻找重复的数，如果在集合中那么就是重复的数，如果不在集合中，就添加到集合。

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        h_set=set()
        for i in nums:
            if i in h_set:return i
            else:h_set.add(i)
1
2
3
4
5
6

剑指 Offer 04. 二维数组中的查找

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

示例:现有矩阵 matrix 如下：[
[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。

代码思路：

1. 暴力，我们可以遍历每一个数，如果目标值等于，则可以返回。时间复杂度：$O(nm)$
2. 找规律，我们可以发现，每一行中数字依次增大，每一列中也数字依次增大，即一个数的右边比他大，上边比他小。所以我们通过这个规律可以从左下角开始寻找，如果目标比他大，横坐标加一，比他小，纵坐标加一，这样在时间复杂度$O(n+m)$中可以查到结果。

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        n=len(matrix)
        if n==0:return False
        m=len(matrix[0])
        i,j=n-1,0
        while i>=0 and j<m:
            if matrix[i][j]==target:return True
            elif matrix[i][j]<target:j+=1
            elif matrix[i][j]>target:i-=1
        return False
1
2
3
4
5
6
7
8
9
10
11