Java O(n) time, O(1) space, swap number solution. Explanations


  • 0

    Since the range of integers are from 1 to n, n is the size of array, and there is only one duplicate and one missing, you can realign the array in order using the following method.
    For instance, [2,1,2,4] should become [1,2,2,4] after the swap. When you are swapping the second {2}, you find there is already a {2} in position, so it is the duplicate. And after all the rest numbers are in position, the index which the extra {2} takes is the missing number - 1.

    public int[] findErrorNums(int[] nums) {
        int[] ret = new int [2];
        int i = 0;
        while (i < nums.length) {
            if (nums[i] == i+1) {
                i++;
                continue;
            }
            else {
                if (nums[nums[i]-1] == nums[i]) {
                    ret[0] = nums[i];
                    i++;
                    continue;
                }
                else {
                    swap(nums[i]-1, i, nums);
                }
            }
        }
        for (int j = 0; j<nums.length; j++) {
            if (nums[j] == ret[0] && j+1 != nums[j]) {
                ret[1] = j+1;
            }
        }
        return ret;
    }
    private void swap (int i, int j, int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.