Simple Java Solution - runtime 9ms, Time Complexity O(n), Space Complexity O(n)


  • 1

    Similar to Similar to the problem:
    https://leetcode.com/problems/first-missing-positive
    Solution:
    https://discuss.leetcode.com/topic/8293/my-short-c-solution-o-1-space-and-o-n-time

    The idea is that arr[] was initialized with all 0, when traversing nums[], we use arr[] to store the correct array like arr[i] should store the element i + 1, so nums[i] should be stored in arr[nums[i] - 1]. If we want to store nums[i] in arr[nums[i] - 1], but find that arr[nums[i] - 1] > 0, we know that nums[i] is the duplicate number. Then the missing number should be the one whose value is 0 in arr[]:

    public int[] findErrorNums(int[] nums) {
        	int len = nums.length;
            int[] res = new int[2], arr = new int[len];
            for (int i = 0; i < len; i++) {
                if (arr[nums[i] - 1] == nums[i]) res[0] = nums[i];
                else arr[nums[i] - 1] = nums[i];
            }
            for (int i = 0; i < len; i++)
                if (arr[i] == 0) res[1] = i + 1;
            return res;
    }
    

Log in to reply
 

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