448. Find All Numbers Disappeared in an Array (Easy)

https://leetcode.com/problems/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]

Solutions

class Solution {

    // bind the element value to specific array slot, say value 1 placed in index 0,
    // value n placed in index n - 1. This means when we come across certain slot with
    // undesired value, we need to swap it to its corresponding slot.

    public List<Integer> findDisappearedNumbers(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }

        // go through the nums elements
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == Integer.MAX_VALUE) {
                continue;
            }

            // set the duplicate value to max integer. For instance, nums[3] = 5,
            // nums[4] = 5, set nums[3] = Integer.MAX_VALUE
            if ((nums[i] != i + 1) && (nums[nums[i] - 1] == nums[i])) {
                nums[i] = Integer.MAX_VALUE;

                // move on processing
                continue;
            }

            // For current slot, a new value will be swapped in, if also not conform our rule,
            // swap it again until every slot meets our requirements.

            // For example, num[3] = 5, swap value on 3 to nums[3] - 1
            if (nums[i] != i + 1) {

                swap(nums, i, nums[i] - 1);

                // Do not move on. Process the swapped in element
                i--;
            }
        }

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

        return ans;
    }

    private void swap(int[] nums, int x, int y) {
        int tmp = nums[y];
        nums[y] = nums[x];
        nums[x] = tmp;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""