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.

Example:

思路:由于元素大小有限制,是在1..n之间。

这个信息有两个作用。一个是元素都是正数,一个是元素大小(绝对值意义上的)有限。

因此我们可以把元素本身和一个位置关联起来。

由于都是正数,我们可以用变成其相反数的方法进行标记(如果已经为负数,就不做处理)

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz