Java O(n) time O(1) Space, same with First Missing Positive


  • 0
    F

    This problem is very similar to "First Missing Positive"

    The target is to put each number in correct position.
    For example,
    [2, 1, 2, 4]
    After traverse the array for the 1st time, we get [1, 2, 2, 4]
    In the 2nd round, we find whether nums[i] == i + 1.
    If nums[i] != i + 1, the duplicate number is nums[i], the missing number is i + 1. Then return the answer.

    class Solution {
        public int[] findErrorNums(int[] nums) {
            // very similar to first missing postive
            if (nums == null || nums.length == 0) {
                return new int[0];
            }
            int[] res = new int[2];
            for (int i = 0; i < nums.length; i++) {
                while (nums[nums[i] - 1] != nums[i]) {
                    swap(nums, nums[i] - 1, i);
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != i + 1) {
                    res[0] = nums[i];
                    res[1] = i + 1;
                    break;
                }
            }
            return res;
        }
        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

  • 0
    F

    Here's the "First Missing Positive" problem and my solution.

    **Given an unsorted integer array, find the first missing positive integer.

    For example,
    Given [1,2,0] return 3,
    and [3,4,-1,1] return 2.

    Your algorithm should run in O(n) time and uses constant space.**

    public class Solution {
        public int firstMissingPositive(int[] nums) {
            // to put each number in its right place
            for(int i = 0; i < nums.length; i++) {
                while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                    swap(nums, nums[i] - 1, i);
                } 
            }
            for(int i = 0; i < nums.length; i++) {
                if(nums[i] != i + 1) {
                    return i + 1;
                }
            }
            return nums.length + 1;
        }
        public void swap(int[] nums, int i, int j) {
            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.