leetcode with python:448. Find All Numbers Disappeared in an

题目:

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

给定一长度为n的阵列nums,其元素值的範畴在1~n
找出1~n所有不在nums内的元素,放在一阵列内回传

我採取最直观的做法

class Solution:    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:        ans=[]        numset=set(nums)        for i in range(1,len(nums)+1):            if i not in numset:                ans.append(i)                return ans

设立一个nums的set(numset),接着一个一个确认1~n的值是否在numset内
不在就放入ans内,最后回传ans
最后执行时间365ms(faster than 91.74%)

说实在的,这其实是在找nums和range(1,len(nums)+1)两set的差集

class Solution:    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:        return set(range(1,len(nums)+1)) - set(nums)

于是我们直接将两set相减回传
最后执行时间360ms(faster than 93.16%)

题目随后提出一个挑战

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

题目要求我们写出不用额外记忆体且複杂度为O(n)的解
我没有头绪,但我在讨论区看到一个堪称巧妙的解法如下

class Solution:    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:        for i in nums:                nums[abs(i)-1]=-abs(nums[abs(i)-1])        ans=[]        for i in range(len(nums)):            if nums[i]>0:                ans.append(i+1)                        return ans

根据题目的叙述,我们可以知道nums是不会有负数的
这个解法就是运用这一点结合index来记录出现过的值

一开始先遍历一次nums
将index为abs(出现的值)-1的值加上一个负号,纪录出现的值的存在
加上我们有套绝对值,所以不用担心因为更动漏看值

接着我们再遍历一次nums,发现正数时
表示该正数的index+1不在nums内
将index+1放入ans,最后回传ans
最后执行时间397ms(faster than 83.43%)

今天比较忙,更一题就好

那我们下题见