Python算法题集_移动零

本文为Python算法题集之一的代码示例

题目283：移动零

说明：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

注意 ，必须在不复制数组的情况下原地对数组进行操作

本文给出四种解法，结果均正确，不过只有一个是合乎题意的

1. Python3.7以上新特性，代码简洁优雅，结果正确，但技术过于先进，此题不认可

   from itertools import groupby
   
   def move_zeros_to_end_ext3(nums):
       if len(nums) < 2:
           return nums
       return [i for k, g in groupby(nums) if k != 0 for i in g] + [i for k, g in groupby(nums) if k == 0 for i in g]
   
   print(move_zeros_to_end_ext3([0, 1, 0, 3, 12]))
   # 运行结果
   [1, 3, 12, 0, 0]
   

2. 使用数组复制，结果正确，违反限制，此题不认可

   def move_zeros_to_end_ext2(nums):
       if len(nums) < 2:
           return nums
       zeros = []
       non_zeros = []
       for num in nums:
           if num == 0:
               zeros.append(num)
           else:
               non_zeros.append(num)
       return non_zeros + zeros
   
   print(move_zeros_to_end_ext2([0, 1, 0, 3, 12]))
   # 运行结果
   [1, 3, 12, 0, 0]
   

3. 从后往前进行块移动，结果正确，步骤最长，超时失败

   def move_zeros_to_end_timeout(nums):
       if len(nums) < 2:
           return nums
       left, right = len(nums) - 2, len(nums) - 1
       while right > 0:
           if nums[right] == 0:
               right -= 1
               left = right -1
               continue
           while left >= 0:
               if nums[left] == 0:
                   for iIdx in range(right - left):
                       nums[left+iIdx] = nums[left+iIdx+1]
                   nums[right] = 0
                   right -= 1
                   left = right - 1
                   continue
               left -= 1
           right -= 1
           left = right - 1
       return nums
   
   print(move_zeros_to_end_timeout([0, 1, 0, 3, 12]))
   # 运行结果
   [1, 3, 12, 0, 0]
   

4. 使用零数量计数器，所有元素最多移动一次，结果正确，通过算法验证

   def move_zeros_to_end_ext1(nums):
       if len(nums) < 2:
           return nums
       iZeroCount = 0
       left, right = 0, len(nums) - 1
       while left <= right:
           if nums[left] == 0:
               iZeroCount += 1
           else:
               nums[left - iZeroCount] = nums[left]
           left += 1
   
       left -= iZeroCount
       while left <= right:
           nums[left] = 0
           left += 1
       return nums
   
   print(move_zeros_to_end_ext1([0, 1, 0, 3, 12]))
   # 运行结果
   [1, 3, 12, 0, 0]
   

第四种解法效果还行，如图

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~