Java accepted simple solution


  • 151
    M

    The basic idea is that we iterate through the input array and mark elements as negative using nums[nums[i] -1] = -nums[nums[i]-1]. In this way all the numbers that we have seen will be marked as negative. In the second iteration, if a value is not marked as negative, it implies we have never seen that index before, so just add it to the return list.

        public List<Integer> findDisappearedNumbers(int[] nums) {
            List<Integer> ret = new ArrayList<Integer>();
            
            for(int i = 0; i < nums.length; i++) {
                int val = Math.abs(nums[i]) - 1;
                if(nums[val] > 0) {
                    nums[val] = -nums[val];
                }
            }
            
            for(int i = 0; i < nums.length; i++) {
                if(nums[i] > 0) {
                    ret.add(i+1);
                }
            }
            return ret;
        }
    

  • 6

    Thanks ,but can somebody tell me what does nums[nums[i] -1] mean? it seems like the index of the array. However if i have an array of [1,1,2,4],as for the array element 2, how could Math.abs(2 ) -1 represents the index of the 3rd element in the array@mnv.koundinya


  • 8
    M

    @wxl163530 In your case [1,1,2,4] index of element 2 would be Math.abs(2) - 1 = 1, i.e., arr[1] would be marked negative. It does not represent the 3rd element in the array.


  • 3
    J

    @mnv.koundinya
    The index of the result array represent each number within 1 and n inclusive. If it is marked as negative, that means that number/index exists in that array.


  • 0
    G

    Subtracting by 1 is so that we can map all integers from 1 to n using the current array (array indexing starts at 0 so value 1 in the array maps to 0 index etc.)


  • 0
    M
    This post is deleted!

  • 0
    T

    Hi,

    The solution gave me an index out of bounds for the input [1,3,4].
    When the element is 4, if we tried to call nums[3], the algorithm failed
    and returns an index out of bounds issue.

    For my solution, I did it with O(n) with O(n) space. I used a boolean array to keep track of whether an element appeared in the nums array or not. i made the boolean array's size as: nums.length+2. My algorithm returned 2, which is the correct answer.

    Can you please look into this issue? Much appreciated!


  • 1

    @turokdaniel [1, 3, 4] is an invalid input, since the upper boundary should be the size of the array, which in this case is 3.


  • 0

    这真是个好主意,比我自己的简单的太多了,本来以为是一个图论的问题呢


  • 3

    @tiankonghewo why would you insist on talking in Chinese...though you can read and understand english..


  • 33

    @wxl163530 因为满世界都是英文,为什么就不能有一点的中文?


  • 0
    This post is deleted!

  • 33
    B

    @tiankonghewo This is a place for everybody to discuss algorithms, no matter where they're from and what language they speak. Please respect others and post useful comments. Your second comment is extremely arrogant and ignorant. If you wanna speak Chinese, go to a Chinese website. Leetcode has helped us a lot and we should return the favor by helping it become more international.


  • 0
    T

    @Heronalps Ahhhh, I see. Thank you :)


  • 0
    R
    This post is deleted!

  • 0
    S

    I have a solution almost the same with yours, but the time it took is around 20ms which only beated 0.22% of all the answers. Below is my code:

    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null)
            return result;
        for (int i = 0; i < nums.length; i++){
            int mapIndex = Math.abs(nums[i]) - 1;
            nums[mapIndex] = nums[mapIndex] > 0 ? -nums[mapIndex] : nums[mapIndex];
        }
        
        for (int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                result.add(i+1);
            } else {
                nums[i] = -nums[i]; // restore the input
            }
        }
        
        return result;
    }

  • 0
    J

    @tiankonghewo 傻逼


  • 0
    T

    great one! I was struggling with the extra space condition, this helps a lot!


  • 0

    Is the solution share some knid of similar idea with bucket sorting? I guess it is trying to mapping the current array into a new one and browser the new array afterwards to check the validility of each element.


  • 0
    W

    @shilongz said in Java accepted simple solution:

    for (int i = 0; i < nums.length; i++){
    if(nums[i] > 0){
    result.add(i+1);
    } else {
    nums[i] = -nums[i]; // restore the input
    }
    }

    because you do many meaningless things


Log in to reply
 

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