448. Find All Numbers Disappeared in an Array

##问题描述

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.

##思路

一个个过`nums`中的数字,因为题目中限制每个数字都大于`1`,所以我们通过改变以`nums`中的数字的值为`index`的数字的正负号(凡是大于`0`的都改成负的)得到一个`list`,该`list`中每个`index`位置的值如果大于`0`,说明改数字没被access过,是缺失的数字,返回`index+1`

```

    def findDisappearedNumbers(self, nums):

        """

        :type nums: List[int]

        :rtype: List[int]

        """

        for i in range(len(nums)):

            index = abs(nums[i])-1

            if nums[index]>0:

                nums[index] = -nums[index]

        return [j+1 for j in range(len(nums)) if nums[j]>0]

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容