Java

import java.util.ArrayList;
import java.util.List;

/**
 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]
 */

public class Find_All_Numbers_Disappeared_in_an_Array {

    public static void main(String[] args) {

        Find_All_Numbers_Disappeared_in_an_Array out = new Find_All_Numbers_Disappeared_in_an_Array();
        Solution s = out.new Solution();

        int[] a = new int[]{4,3,2,7,8,2,3,1};
        System.out.println(s.findDisappearedNumbers(a));
    }

    class Solution {
        public List<Integer> findDisappearedNumbers(int[] nums) {

            // put value to its index position, value x should be at index x-1
            // key is to handle duplicate

            int i = 0;
            int missingCount = 0;
            while (i < nums.length) {
                if (nums[i] > nums.length) {
                    i++;
                } else if (nums[i] != i + 1) {
                    // check duplicate
                    if (nums[nums[i] - 1] == nums[i]) {
                        // find dup
                        nums[i] = nums.length + 1; // @key: mark outlier //@key: better mark it as negative, to avoid wrong answer
                        missingCount++;
                    } else {
                        // switch
                        int tmp = nums[nums[i] - 1];
                        nums[nums[i] - 1] = nums[i];
                        nums[i] = tmp;
                    }
                } else if (nums[i] == i + 1) {
                    i++;
                }
            }

            List<Integer> result = new ArrayList<>();
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] > nums.length) {
                    result.add(j + 1);
                }
            }

            return result;
        }
    }
}

Java

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            while (nums[i] != i + 1) {
                if (nums[i] == nums[nums[i] - 1])
                    break;
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        List<Integer> disappearedNumbers = new ArrayList<Integer>();
        for (int i = 0; i < length; i++) {
            if (nums[i] != i + 1)
                disappearedNumbers.add(i + 1);
        }
        return disappearedNumbers;
    }
}

All Problems

All Solutions