O(n) python solution beats 100%


  • 0
    C

    find 0, pop it out and add 0 in the end

    class Solution(object):
        def moveZeroes(self, nums):
            if not nums: return
            length = len(nums)
            i = length-1
            j = 0
            while i >= 0:
                if nums[j] == 0:
                    nums.pop(j)
                    nums.append(0)
                else:
                    j += 1
                i -= 1
    

  • 1
    S

    Seems it's not 'in place'. Actually the pop and append change the array itself. Right?


  • 0
    C

    hmmmm, not sure about that

    what I found on wiki:

    In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements.

    people usually do swap, but it's slow compared with pop and append. I think my method is kind of replacement?


  • 0
    S

    @cslns Sounds reasonable! But if in some other languages like java, there are no 'pop' and 'append' methods in the 'array' class. If implementing these two methods ourself, array structure (int[] nums) maybe can only use "swapping" way, linkedlist structure can adopt "replacement" way like your solution. I'm not sure if converting array to linkedlist whether or not broken the 'in place' rule?


  • -1
    V

    This solution seems a little tricky, lol
    Here is another bests 100% solution,

    class Solution(object):
    def moveZeroes(self, nums):
    length = len(nums)
    if length == 0:
    return
    new_index = 0
    index = 0
    while index < length:
    if nums[index] != 0:
    temp = nums[index]
    nums[index] = 0
    nums[new_index] = temp
    new_index += 1
    index += 1
    return


  • 1

    @cslns said in O(n) python solution beats 100%:

    people usually do swap, but it's slow compared with pop and append.

    Only because the judge's test cases are pretty small. Try for example nums = [0, 1] * 200000 and your solution will take several seconds while the "usual" solutions take only a small fraction of a second.

    Btw, another big reason why you were able to beat 100% is that the system recently got faster and the old times haven't been deleted yet.


  • 0
    C

    @StefanPochmann good point. You are right.


Log in to reply
 

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