【leetcode】找到所有数组中消失的数字

找到所有数组中消失的数字

问题描述：

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

初次解法

按顺序遍历，把不在数组里的值添加到结果的数组里。

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

问题：每一次判断 not in 都是在遍历，时间消耗大。

如下：

报错输入实例：

此解法的优化
遍历数组的复杂度o(n) 遍历字典和哈希表的复杂度o(1)
因此我们建立一个哈希表来进行查找是否出现过，可以大大减少时间复杂度。

class Solution(object):
    def findDisappearedNumbers(self, nums):
        hash_table = {}
        for num in nums:
            hash_table[num] = 1
        result = []    
        for num in range(1, len(nums) + 1):
            if num not in hash_table:
                result.append(num)              
        return result      

结果

缺点：新建了哈希表，有了额外的内存消耗

进一步优化

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

解法二
set()集合： difference方法 可以求两个集合的差集。

class Solution(object):
    def findDisappearedNumbers(self, nums):
       return set([i+1 for i in range(len(nums))]).difference(set(nums))

解法三

标记出现过的数字，将出现过的数字置为负数，输出正数即为消失的数字。

class Solution(object):
    def findDisappearedNumbers(self, nums):
        res=[i+1 for i in range(len(nums))]
        for i in nums:
            res[i-1]=-abs(res[i-1])       
        r=res.copy()
        for m in res:
            if m<0:
               r.remove(m)
        return r

tips：

1. 对数组进行遍历和操作时，尽量复制了以后再操作，remove元素以后，后面的元素前移，但是索引号是按顺序遍历，做不到全部遍历。
2. 对列表的元素进行删除：
   （1）del：根据索引值删除元素 del res[i]
   （2）remove:根据元素值删除元素 res.remove(m)
   （3）pop: 类似于栈的出栈
   （4）clear：删除列表所有元素

问题 超过了时间限制
改进

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

删除元素首先要遍历数组，找到该元素才能删除，但是加入元素不需要遍历，所以大大提升了速度。
但是这个方法还是开辟了新的空间，内存消耗大。

优化解：

在原数组上进行修改，数字是几，就将对应索引号的数置负

然后遍历，正数的索引号就是没有出现的数字。

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

时间复杂度o(n)
空间复杂度o(1) 没有开辟新的空间