E-448. Find All Numbers Disappeared in an Array

E

Loading...LeetCode

暴力：O(n^2), ETL

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

改进1: T: O(n), S: O(n)：

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

# 因为我们只需要遍历n次来达到循环，所以上面代码中的comp_set不必是个set，普通的range就行。        
# 更好的写法：
class Solution(object):
    def findDisappearedNumbers(self, nums):
        marked = set(nums)
        return [i for i in range(1, len(nums)+1) if i not in marked]

改进2：T: O(n), S: O(1):

"""
    既然要空间复杂度为常数，就不能开新的数据结构记录“是否出现”这一信息，从而就要思考如何用
    原有的nums来存储这一额外信息。
    
    从而我们发现数组除了每一项存数字这一本身信息之外，还能通过正负来传达额外信息。
    
    再加上因为我们只能操作这一个nums这个list，而nums的操作无非就是
        1.索引获取nums某项的值, 即 new_value = nums[index]
        2.更改nums每一项的值, 即   nums[index] = new_value
    
    注意题中条件: 1 ≤ a[i] ≤ n 包含的信息：
        1. value为正数
        2. value最大不超过a的长度
        3. 所以, 通过value-1如果作为索引来进行某些操作应该是潜在的可选正确的方向
    
    接着, 我们发现如果nums中, 从1到len(nums)都有出现, 那么我们遍历nums一遍, 把每一项的内容减
    去1作为index, 把每一个nums[index]都变为负数, 经过这样处理之后的nums每一项会变为负数.
    
    从而我们发现, 如果nums中, 如果缺失某些1到len(nums)的值, 那么我们遍历nums一遍, 采取上面
    同样的操作, 那么最终nums的会有些项依旧为正数(而有些nums项的值会被赋多次(此题中是2次)负值,
    但是我们只用保证,只要出现过一次,就使其永远为负值,所以我们要用-abs(nums[index])来赋值), 这些
    正数项的下标+1(即index+1)正是缺失的值.
    
    通过上述方法遍历之后，我们再次遍历一次更改值之后的nums, 找出下标为正数的值的下标, 通过list
    输出即可.
"""

# pythonic:
def findDisappearedNumbers(self, nums):
    for num in nums:
        index = abs(num) - 1 # 注意这个num可能在之前已经成负数了, 所以需要用abs取绝对值
        nums[index] = -abs(nums[index])
            
    return [i + 1 for i, num in enumerate(nums) if num > 0]

我的最终答案:

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in nums:
            index = abs(i) - 1
            nums[index] = -abs(nums[index])
        
        return [i + 1 for i,v in enumerate(nums) if v > 0]

拓展阅读:

enumerate用法