leetCode#448. Find All Numbers Disappeared in an Array

本文主要是介绍leetCode#448. 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]

Code

class Solution(object):def findDisappearedNumbers(self, nums):""":type nums: List[int]:rtype: List[int]"""exist = [0] * (len(nums) + 1)for i in nums:exist[i] = 1res = []for idx, i in enumerate(exist):if idx != 0 and i == 0:res += [idx]return res

author:yang2007chun
For each number i in nums,
we mark the number that i points as negative.
Then we filter the list, get all the indexes
who points to a positive number.
Since those indexes are not visited.

class Solution(object):def findDisappearedNumbers(self, nums):""":type nums: List[int]:rtype: List[int]"""# For each number i in nums,# we mark the number that i points as negative.# Then we filter the list, get all the indexes# who points to a positive numberfor i in xrange(len(nums)):index = abs(nums[i]) - 1nums[index] = - abs(nums[index])return [i + 1 for i in range(len(nums)) if nums[i] > 0]

Conclusion

我的算法还算是本科时期的产物，先统计存在的，再遍历出不存在的，这样其实空间没有达到要求。精简的算法，都是直接修改原始list，比如设为负数。然后最后再遍历原始list即可。这点学习到了。

这篇关于leetCode#448. Find All Numbers Disappeared in an Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---