pythonswapcopy-and-swap

swap elements in an array causing issue


Happy New Year. I have a question about swapping elements in an array under Python environment. The code w/o issues are:

def findMissingNumber(nums):
    length = len(nums)
    result = []
    i = 0
    while i < length:
        # num = nums[i]
        target = nums[i] - 1
        if nums[i] != i+1 and nums[i] != nums[target]:
            # swap with the nums[i]-1
            nums[target], nums[i]= nums[i], nums[target]
        else:
            i += 1
    for j in range(length):
        if nums[j] != j+1:
            result.append(j+1)
    return result

print(findMissingNumber([2, 3, 1, 8, 2, 3, 5, 1]))
print(findMissingNumber([2, 4, 1, 2]))
print(findMissingNumber([2, 3, 2, 1]))

with answer:

[4, 6, 7]
[3]
[4]

The wrong one is:

def findMissingNumber(nums):
    length = len(nums)
    result = []
    i = 0
    while i < length:
        num = nums[i]
        target = num - 1
        if num != i+1 and num != nums[target]:
            # swap with the num-1
            nums[target], num = num, nums[target]
        else:
            i += 1
    for j in range(length):
        if nums[j] != j+1:
            result.append(j+1)
    return result

print(findMissingNumber([2, 3, 1, 8, 2, 3, 5, 1]))
print(findMissingNumber([2, 4, 1, 2]))
print(findMissingNumber([2, 3, 2, 1]))

with answer:

[4, 6, 7]
[3, 4]
[3, 4]

I am not sure why the reference (should I call that) causing trouble. Would you mind explaining it in detail.
Thanks.


Solution

  • Fixed code with comments.

    def findMissingNumber(nums):
        length = len(nums)
        result = []
        i = 0
        while i < length:
            # num and nums[i] have the same value but doesnt refer to same memory location
            num = nums[i]
            target = num - 1
            if num != i+1 and num != nums[target]:
                # swap with the num-1
                
                # incorrect swap, num value is not referencing the list index, but has a copy of its value,
                # so instead of swapping value with num, do it from the list like below
                # nums[target], num = num, nums[target]
                
                
                # correct swap
                nums[target], nums[i] = nums[i], nums[target]
            else:
                i += 1
        for j in range(length):
            if nums[j] != j+1:
                result.append(j+1)
        return result
    
    print(findMissingNumber([2, 3, 1, 8, 2, 3, 5, 1]))
    print(findMissingNumber([2, 4, 1, 2]))
    print(findMissingNumber([2, 3, 2, 1]))