Find All Numbers Disappeared in an Array

• LeetCode: Find All Numbers Disappeared in an Array

• Problem:

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.

• Examples:

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

Output:
[5,6]

• Analysis:

The concept is like bucket sort. 

Make the array fit the rule "arr[i] = i + 1"

• Code - Java:

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

• Code - C++:

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int len = nums.size();
        vector<int> result;
        for (int i = 0; i < len; i++) {
            int temp = nums[i];
            while (temp != nums[temp - 1]) {
                int temp1 = nums[temp - 1];
                nums[temp - 1] = temp;
                temp = temp1;
            }
        }
        for (int i = 0; i < len; i++) {
            if (i + 1 != nums[i]) {
                result.push_back(i + 1);
            }
        }
        return result;
    }
};

• Code - Python:

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        numLen = len(nums)
        result = []
        for i in range(numLen):
            temp = nums[i]
            while temp != nums[temp - 1]:
                temp1 = nums[temp - 1]
                nums[temp - 1] = temp
                temp = temp1
        for i in range(numLen):
            if (i + 1) != nums[i]:
                result.append(i + 1)
        return result

• Time Complexity: O(N), N is the length of input array
• Space Complexity: O(M), M is the length of output array