O(n)solution in 1 loop, no extra space


  • 0

    The idea is, cuz we know the value of each element is bounded, and the range is 1~n, which is just the range of index 1~n of the input array, then each time when we met a new element nums[i], we can just throw it to the "place it should be", which has the index = nums[i].
    In the meantime we don't wanna lose track of each original element at index nums[i], so we just make a mark at that place!
    Simply let nums[index] = -nums[index], where index = nums[i].
    Math.abs(nums[i]) is the original element nums[i] that is not marked yet.
    Then every time, if we find that nums[index] is already marked, we must encounter a duplicate nums[i], which leading us to the same place that we've marked before.

    public int findDuplicate(int[] nums) {
        for(int i = 0;i<nums.length;i++){
            int index = Math.abs(nums[i]);
            //in case we find the dupicate
            if(nums[index]<0) return index;
            nums[index]=-nums[index];
        }
        //If we don't find it then return default value, could be anything.
        return 0;
    }

  • 0
    Z

    @tongzhou2 You have modified the array. The NOTE is "You must not modify the array (assume the array is read only)."


  • 0

    @zhongtaovip Yes you're right I didn't notice that before.


Log in to reply
 

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