Time O(n) and space O(1)


  • 0
    C
    int findDuplicate(int* nums, int numsSize) {
    int index = 0;
    for(int i=0; i < numsSize; i++) {
        index = nums[i] > numsSize ? nums[i] - numsSize: nums[i];
        if(nums[index] > numsSize) {
            return index;
        } else {
            nums[index] = nums[index] + numsSize;
        }
    }
    return 0; }

  • 0
    R

    you are modifying the array. The problem statement says "You must not modify the array".


  • 0
    C

    It's easy to recover the array , because every item is not larger than numsSize(the n) .So you can iterate the array , use the larger one minus the numsSize .

    for ... loop {
    if (item > numsSize) item -= numsSize;
    }


Log in to reply
 

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