土豆炒青椒
土豆炒青椒

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

刷到天亮

基本信息

  • 题号: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 不占空间



总结

  • 无 😭
CC BY-NC-ND 2.0 版权声明

喜欢我的文章吗?
别忘了给点支持与赞赏,让我知道创作的路上有你陪伴。

加载中…

发布评论