CODEWITHSUNDEEP
python
summer
summer

Reputation: 65

Python: fail to swap two elements in a list

Is there anyone can help me to have a look at this code. I am trying to solve the first missing positive question in leetcode. But this code cause an endless loop as I found I fail to swap the A[i] and A[A[i]-1]. But I have test to swap to elements in list using this simple code:

A = [2,1]
A[0], A[1] = A[1], A[0]
print A # A = [1,2]

I do not know what the mistake is :(

def firstMissingPositive(self, A):
    i = 0
    length = len(A)
    while i < length:
        if A[i] >= 1 and A[i] <= length:
            if A[i] != i+1 and A[A[i]-1] != A[i]:
                A[i], A[A[i]-1] = A[A[i]-1], A[i]
            else:
                i += 1
        else:
            i += 1
    for i in range(length):
        if A[i] != i+1:
            return i+1
    return length + 1

Upvotes: 0

Views: 118

Answers (1)

jwodder
jwodder

Reputation: 57470

You're modifying A[i] during the execution of the assignment statement, and so the evaluation of A[A[i]-1] on the left-hand side of the = won't evaluate the way you're expecting it to. You need to change this:

A[i], A[A[i]-1] = A[A[i]-1], A[i]

to this:

tmp = A[i]-1
A[i], A[tmp] = A[tmp], A[i]

This phenomenon is addressed by a note in the Python Language Reference:

WARNING: Although the definition of assignment implies that overlaps between the left-hand side and the right-hand side are 'safe' (for example a, b = b, a swaps two variables), overlaps within the collection of assigned-to variables are not safe! For instance, the following program prints [0, 2]:

x = [0, 1]
i = 0
i, x[i] = 1, 2
print x

Upvotes: 5

Related Questions