Python solution 39 ms


  • 0
    B
    class Solution(object):
        def sortColors(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """ 
            i = 0
            length = len(nums)
            while (i < length):
                if nums[i] == 0:
                    nums.insert(0, nums[i])
                    del nums[i + 1]
                    i = i + 1
                elif nums[i] == 2:
                    nums.append(nums[i])
                    del nums[i]
                    length = length - 1
                else:
                    i = i + 1

  • 0
    W

    Is this really o(N) in time? I think del nums[i] is an o(N) operation, which would make sense as list does not allow random access of elements. Also, though append is o(1), is insert(i, sth) o(N) due to the same reason?


  • 0
    B

    Yes you are right. Maybe we can make this example as a mistake example.


Log in to reply
 

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