各位题友大家好！今天是 @负雪明烛 坚持日更的第 20 天。今天力扣上的每日一题是「448. 找到所有数组中消失的数字」。

解题思路

今天这个题目是说：给出的数组中每个元素的范围都是 $[1, n]$，数组长度为 $n$。数组中有些元素出现了 2 次，有些元素出现了 1 次，有些没出现。求数组中没有出现的数字。

重点1：数组长度是 $n$；
- 重点2：每个数字的范围都是 $[1, n]$。

方法一：遍历寻找 $1~n$ 是否在数组中存在

本题最简单的方法就是，对 $1~n$ 的所有数字进行遍历，判断每个数字是否在数组中存在。

问题是如何快速判断数字在数组中存在吗？可以使用 set 数据结构，它的查找时间复杂度可以降低到 $O(1)$。

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        counter = set(nums)
        N = len(nums)
        res = []
        for i in range(1, N + 1):
            if i not in counter:
                res.append(i)
        return res

时间复杂度：$O(N)$，用时296ms，击败了99.37%的用户；
空间复杂度：$O(N)$，空间22.3M，击败了34.24%的用户。

方法二：数组的原地操作

题目更高阶的要求不使用额外的空间。这增加了难度。

如果题目是「每个数字都出现了 2 次，只有一个数字出现了 1 次」，你会做吗？这是题目136. 只出现一次的数字。朋友们应该都知道可以用异或。而本题中每个数字出现的次数可以是 $0/1/2$ 次，已经无法用异或了。

真正求解本题需要用到一个奇技淫巧：原地修改数组。

这个思想来自于长度为 $N$ 的数组可以用来统计 $1~N$ 各数字出现的次数；题目给出的数组的长度正好为 $N$，所以可以原地修改数组实现计数。

当前元素是 $nums[i]$，那么我们把第 $nums[i] - 1$ 位置的元素乘以 -1，表示这个该位置出现过。当然如果第 $nums[i] - 1$ 位置的元素已经是负数了，表示 $nums[i]$ 已经出现过了，就不用再把第 $nums[i] - 1$ 位置的元素乘以 -1。最后，对数组中的每个位置遍历一遍，如果 $i$ 位置的数字是正数，说明 i 未出现过。

这个方法对应的 Python 代码如下。

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for i, num in enumerate(nums):
            if nums[abs(num) - 1] > 0:
                nums[abs(num) - 1] *= -1
        res = []
        for i in range(len(nums)):
            if nums[i] > 0:
                res.append(i + 1)
        return res

刷题心得

本题要求不使用额外空间，考虑原地修改数组用来节省额外空间，在 LeetCode 算法题中偶尔会用到这个技巧。
2. 该技巧属于奇技淫巧，在实际工作中很少用到。

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】448. 找到所有数组中消失的数字

解题思路

方法一：遍历寻找 $1~n$ 是否在数组中存在

方法二：数组的原地操作

刷题心得