JAVA O(1) SPACE O(n) Time using the sign as the boolean flag.


  • 0
    L

    ...
    public class Solution {
    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> res = new LinkedList<Integer>();
        
        int temp = 0;
        
        for(int i = 0; i < nums.length; i++) {
            temp = Math.abs(nums[i]);  
            if (nums[ temp -1] < 0){
                res.add(temp);
            }else {
                nums[temp-1] = ~nums[temp-1] + 1;
            }
            
        }
        return res;
    }
    

    }

    ...


  • 0
    X

    @lzb0309 you know, while you commit the code, you should give your explanation. so would you please explain your code?


  • 0
    L

    Intuitively , we can use
    ...
    boolean[] flag = new boolean[n];
    ...

    to indicate whether the value n have appeared in the array. However , we are not allowed to use extra space. Since all the nums value are ranged from 1 to n. We can use the "+/-" value at position n to subsititude the boolean[] flag.


  • 0

    Why ~nums[temp-1] + 1 instead of -nums[temp-1]?


  • 0
    L

    @StefanPochmann just wanna get used with the bit manipulation.


Log in to reply
 

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