#448. Find All Numbers Disappear

[TOC]

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/#/description

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

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

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

翻译

• 理想时为打乱的[1,2,3...n]，但是有的数字出现两次，占据了位置，导致有的数字没出现
• 返回没出现的数字

思路

• 以num[0] = 4为例，其理想时出现位置应该为num[3]，即num[abs(num[0]) - 1],所以我们将num[3]位置的数先取绝对值在取反。
• 先取绝对值的原因是，因为该元素可能已经出现，导致num[3]已经变为负数了，直接取反将变回初始状态。
• 循环上述步骤，num中一些数字大于零，有些小于零，输出大于零的数的下标即可。

# Time O(2n) = O(n)
class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for num in nums:
            nums[abs(num) - 1] = -abs(nums[abs(num) - 1])
        return [i + 1 for i, v in enumerate(nums) if v > 0]