My 1ms java code O(n) time, O(1) space


  • -4
    L

    transverse the array from left to right

    after process the index i, the index i has the right value (i+1)

    if nums[i]==i+1, i++

    if nums[i] == nums[nums[i]] or nums[i]<i+1, duplicate number exists

    else swap(nums[i],nums[nums[i]])

    public int findDuplicate(int[] nums) {
        int i = 0, len = nums.length;
        while (i<len) {
            if (nums[i]==i+1) {
                i++;
            } else if (nums[i]<i+1) {
                break;
            } else if (nums[i]==nums[nums[i]]) {
                break;
            } else {
                swap(nums,i,nums[i]);
                
            }
        }
        return nums[i];
    }
    
    private void swap(int[] array,int i,int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

  • 0
    J

    your solution is wrong. You must not modify the array (assume the array is read only).


Log in to reply
 

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