Python one-pass - insert 0 at the beginning, and 2 at the end


  • 0
    L

    class Solution(object):

    def sortColors(self, nums):
        curr = 0
        for _ in range(len(nums)):
            if nums[curr] == 0:
                x = nums.pop(curr)
                nums.insert(0, x)
                curr += 1
            elif nums[curr] == 1:
                curr += 1
            else:
                x = nums.pop(curr)
                nums.append(x)

  • 0

    What's the point of being "one-pass" if it's so very inefficient?


  • 0
    L

    I also tried the following solution but it only beat 19%. But my solution beat 39%.
    So I think for python the built-in pop/insert might be more efficient than assignment.

    https://leetcode.com/discuss/58085/4ms-and-only-5-lines-c-code-without-delete-and-insert

    r = w = b = 0
    for i in range(len(nums)):
    if nums[i] == 2:
    b += 1
    elif nums[i] == 1:
    nums[b] = 2
    nums[w] = 1
    b += 1
    w += 1
    else:
    nums[b] = 2
    nums[w] = 1
    nums[r] = 0
    b += 1
    w += 1
    r += 1


  • 0

    That's because the judge's inputs sadly are tiny. Compare them with let's say nums = [0] * 100000.

    And better format that code. Being Python, it's truly unreadable. You can format in comments just like in questions.


  • 0
    J

    Is it not possible in python to do something like:

     for x in range(0, len(nums)):
            if nums[x] == 0:
                nums.pop(x)
                nums.insert(0, 0)
                x=x-10
            elif nums[x] == 2:
                nums.pop(x)
                nums.append(2)
    

    I was thinking you could reset the x counter somehow (x = x-1) to make sure you don't skip anything but this didn't seem possible?


  • 0
    L

    Your code cannot even pass????
    Input: [1,2,0]
    Output: [1,0,2]
    Expected: [0,1,2]


Log in to reply
 

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