JAVA BEAT 100% only 13ms


  • 0
    A

    For the problem. I think up 2 ways to do it. First is in the comment, both time and space are O(n).

    Then the second way is better. Time is O(n), Space is O(1).

    Assume, we have 1 2 2 4. After the for loop, the array will be [-1, -2, 2, -4]. When you see the second 2, you found the array[2-1] = -2, which is less than 0. So we found the 2 happens two times here.

    After we get [-1,-2,2,-4]. We just go via the whole array, and go check which one is greater than 0. Then the index of that num plus one would be the number we lost in the array. In this case, the index of number 2 is index 2. So the number wo lost is 2 + 1 = 3.

    Thank you!

    public class Solution {

     public int[] findErrorNums(int[] nums) {
        //1.create a int[] with same size. counting sort. get the number with 2. and the number with 0. Time: O(n) space: O(n)
        
        //2. Time: O(n) space: O(1)
        int[] re = new int[2];
        for(int i = 0; i < nums.length; i++){
            if(nums[Math.abs(nums[i]) - 1] < 0)
                re[0] = Math.abs(nums[i]);
            else
                nums[Math.abs(nums[i]) - 1] *= -1;
        }
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                re[1] = i + 1;
                break;
            }
        }
        return re;
        
    }
    

    }


Log in to reply
 

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