83.LeetCode.448. 找到所有数组中消失的数字

• 标签： 数组
• 难度： 中等

• 题目描述

• 我的解法

(对这道题解法的描述，我感觉自己这篇应该是最清晰的了)

可以利用哈希表做计数器，但是题目不允许用额外空间. 可以采取一个十分巧妙的做法。如果我们使用哈希表，那么哈希表的键是 1~ n, 正好对应列表下标 0 ~ n-1。 我们的 列表其实可以看做一个隐式的哈希表：imp = {0：nums[0]， 1：nums[1]，..., n-1: nums[i-1]} . 而且认真考虑后可以发现，我们其实并不需要某个数字的具体计数值，只要知道某个数字出现过即可。我们开始遍历列表， 如果 abs(nums[i]) == 3, 说明包含数字 3, 那么我们只要在上面那个隐式的哈希表中，往 imp[2] 这个篓子里再扔一个标记就好，比如说 - 号， 代表出现了数字 3。 最后我们再次遍历这个列表，或者说隐式哈希表，如果发现某个篓子里没有负号标记， 我们就知道这个篓子代表的那个数字没有出现.

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        results = []
        for n in nums:
            idx = abs(n) - 1
            nums[idx] = - abs(nums[idx])
        for i,n in enumerate(nums):
            if n > 0:
                results.append(i + 1)
        return results

• 其他解法

暂略。