《剑指 offer》刷题记录之一：数组

发表于 2021-08-22 分类于编程与算法，刷题记录阅读次数：本文字数： 1.8k 阅读时长 ≈ 6 分钟

本篇博客为《剑指 offer》一书的刷题笔记（第一部分）。

面试题 3：数组中重复的数字

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

示例

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

限制：\(2 \le n \le 100000\)

思路及代码

题目中的限制可以让我们不用去判断数组是否为空。一种比较简单的方法是先把输入的数组排序，再从排序的数组中找出重复的数字。但是排序一个长度为 \(n\) 的数组一般需要较大的时间与空间复杂度，以归并排序为例，其时间复杂度为 \(O(n\log n)\) ，空间复杂度为 \(O(n)\)。

第二种方法是使用哈希表（哈希集合）。从头到尾按顺序扫描数组的每个数字，每扫描到一个数字的时候，都可以用 \(O(1)\) 的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字，就把它加入哈希表。如果哈希表里已经存在该数字，就找到了一个重复的数字。本方法的时间复杂度为 \(O(n)\)，但是空间复杂度也为 \(O(n)\)。

上述方法的 java 实现如下：

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}

我们还可以利用数组的下标实现一种巧妙的解法。注意到本题中数组的数字都在 0~n-1 的范围内，如果数组中没有重复的数字，那么当数组排序之后数字 \(i\) 将出现在下标为 \(i\) 的位置。如果数组中有重复的数字，则会导致有些位置上存在多个数字，而有些位置则可能没有数字。

基于上述发现，现在我们可以重排这个数组，从头到尾依次扫描数组中的每个数字，当扫描到下标为 \(i\) 的数字时，首先比较这个数字（记作 \(m\)）是不是等于 \(i\)，如果是，则扫描下一个数字；如果不是，则将它和下标为 \(m\) 的数字进行比较，如果它和第 \(m\) 个数字相等，就找到了一个重复的数字（该数字在下标为 \(i\) 和 \(m\) 的位置都出现了）；如果它和第 \(m\) 个数字不相等，就把该数字和第 \(m\) 个数字交换，把 \(m\) 放到属于它的位置，然后重复这个比较、交换的过程（仍在当前位置，只有相等才进位）。该方法的时间复杂度为 \(O(n)\)，因为每个数字最多只要交换两次就能找到属于它的位置；而由于所有的操作都是在原数组上进行的，所以空间复杂度为 \(O(1)\)。

上述方法的 python 实现如下：

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int: # 注意变量注解需要从 typing 导入
        for i in range(len(nums)):
            while (nums[i] != i):
                if nums[nums[i]] == nums[i]: # 如果相等则返回重复数字
                    return nums[i]
                else:
                    temp = nums[nums[i]] # 交换两个位置的数字
                    nums[nums[i]] = nums[i]
                    nums[i] = temp
        return -1 # 不写的话返回 None

如果我们修改题目如下：

在一个长度为 n+1 的数组里所有的数字都在 1~n 的范围内，所以数组内至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。

这道题和原题的区别在于，一定存在重复的数字，且不能修改输入的数组。我们可以创建一个辅助数组，基于同样的思想找出重复数字，但是空间复杂度会变成 \(O(n)\)。如果要减小空间复杂度，由于数组长度为 \(n+1\) 但数字范围为 \(1-n\)，所以即便对数组排序后，将重复数字用缺失的原数字替换，也一定会多出一个重复数字。

基于这一特征，我们可以采用二分查找的思想的方法，将原数组按照数字大小一分为二，分别统计其中数字的个数，如果个数超过数字本身的范围，则一定存在重复，借此不断缩小重复数字出现的范围，最终找出重复数字。这种方法的空间复杂度为 \(O(1)\)，时间复杂度为 \(O(n\log n)\)，但是需要指出，这种方法不能保证找出所有重复的数字（可能某些数字虽然重复但在特定范围内个数并没有超出），这里不做赘述。

面试题 4：二维数组中的查找

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

示例

对于如下矩阵：

[
  [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]
]

给定数字 5，返回 true
给定数字 20，返回 false

思路及代码

这道题如果数组没有排序，可以考虑采用暴力法，遍历二维数组的每一行和每一列，但这样做的时间复杂度为 \(O(n\times m)\)。而由于给定的二维数组具有每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。通过观察发现，如果从右上角开始选取数字来和查找的数字进行比较，那么我们每次可以剔除一行或一列，缩小查找的范围，直到找到查找的数字，或者查找范围为空。下图给出了一个例子：

上述方法的 java 实现如下：

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, cols = matrix[0].length; // 获取二维数组的行数与列数
        int row = 0, col = cols - 1; // 注意与python多个赋值的区别
        while (row < rows && col >= 0) {
            int num = matrix[row][col];
            if (num == target) {
                return true;
            } else if (num > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
}

对应的 python 实现如下：

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if (matrix == None or len(matrix) == 0 or len(matrix[0]) == 0):
            return False
        rows, cols = len(matrix), len(matrix[0])
        row, col = 0, cols - 1
        while row < rows and col >= 0:
            num = matrix[row][col]
            if num == target:
                return True
            elif num > target:
                col -= 1
            else:
                row += 1
        return False

该算法的时间复杂度为 \(O(m+n)\)，因为行下标最多增加 \(n\) 次，列下标最多减小 \(m\) 次。空间复杂度为 \(O(1)\)。实际上，选用左下角的数字也可以实现同样的效果，但是左上角和右下角不行。