「微软」圣诞节后 刷 ～ 找到数组里面丢失的所有数字

基本信息

• 题号：448
• 题厂：微软
• 难度系数：低

已知已知一个数组长度为 n，应该放入 1 ～ n 数字，找到 1 ～ n 中本来应该出现但没有出现的数字

例如 nums = [4,3,2,7,8,2,3,1]
返回 [5,6]。长度为 8， 该放入 1 ～ 8，所以 5、6 缺失

解题思路

• 如果数组长度为 n，即在 index 位 n - 1上的值为 n。
• 可以创建一个长度为 n 的空数组，遍历 nums，如果数字 i 出现，在 i - 1 的 index 位标记

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        container = [0] * len(nums)

        for num in nums:
           container[num - 1] = 1

        res = []
        for i in range(len(container)):
            if container[i] == 0:
                res.append(i + 1)

        return res

lConstraints

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

Follow Up

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

创建空数组的想法可以解决问题，但是因为创建了空数组，用到了额外空间。所以新问题是：如何在不创建新数组的基础上，完成任务？？

解题思路

• 这个时候我们可以引用绝对值标记——因为 contraints 告诉我们数组数字全部为正…——此处我么用 n 在对应 index 为 n - 1 处将绝对值反转，即正数代表没有出现的，负数代表出现过…… 
• 完成正负标记后，再遍历一遍 nums，根据 index 位取值正负判断对应数字有没有出现

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for n in nums:
            i = abs(n) - 1
            nums[i] = -1 * abs(nums[i])

        res = []
        for i in range(len(nums)):
            if nums[i] > 0:
                res.append(i + 1)

        return res

测试

• n = 1 时
• 1 ～ n 全部对应出现时
• ……

Big O

• 时间复杂度：O（n）
• 空间复杂度：优化后 O（1）题目默许返回值 res 不占空间

总结

• 无 😭