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:

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

Output:
[5,6]

题目大意是给定一个数组，最大值为n， n= size of array元素出现一次或两次，还有没有出现的，找到没有出现的元素。

题目要求不开辟额外空间，并且时间复杂度为o(n).这个方法比较巧妙。

该题有一个重要的线索元素的最大值为数组的长度，首先遍历数组，使用nums[nums[i] -1] = -nums[nums[i]-1]将数值置为负，在第二次遍历中，不为负数的就是没有出现的数值。

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        for(int i = 0; i < nums.length; i++)
        {
            int tmp = Math.abs(nums[i]) - 1; //index
            if(nums[tmp] > 0) nums[tmp] = -nums[tmp];
        }
        for(int i = 0;i < nums.length; i++)
            if(nums[i] > 0) l.add(i + 1);
        return result;
    }
}