Requirements:

Given an array of integers in the range 1 ≤ a[I] ≤ n (n = array size), some of the elements appear twice and others only once. Find all numbers in the range [1, n] that do not appear in the array.

Can you do this without using extra space and with O(n) time? You can assume that the returned array is not in the extra space.

Example:

Input: [4,3,2,7,8,2,3,1] output: [5,6]Copy the code

Ideas:

Arrays can be processed in place:

  1. Iterate over the array, because the array is n+1 in length and the number ranges from 1 to n, so you can find the data by subscript.
  2. When you go through the array, you find the place in the array where the number is the index, and if it’s positive, you multiply it by -1, and if it’s already negative, you’ve already found it, so you don’t need to multiply it by -1
  3. One last time, if a number is positive, that number has not been accessed, indicating that the missing number minus one as a subscript access array does not exist

Code:

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i] - 1);
            if (nums[index] > 0) {
                nums[index] *= -1; }}for (int i = 1; i < nums.length; i++) {
            if (nums[i-1] > 0) { res.add(i); }}returnres; }}Copy the code