leetcode283之移动零

题目描述：

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

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes

代码实现：

 1 def moveZeros(nums):
 2     n = len(nums)
 3     for i in range(n):
 4         for j in range(n - i - 1):
 5             if nums[j] == 0:
 6                 nums[j], nums[j + 1] = nums[j + 1], nums[j]
 7 
 8     # return nums
 9 
10 
11 print("-------测试moveSeros()------")
12 nums = [0, 1, 0, 3, 0, 12]
13 moveZeros(nums)
14 print(nums)
15 
16 
17 def moveZeros1(nums):
18     '''
19     双指针法解决
20     :param nums:
21     :return:
22     '''
23     left, right = 0, 0
24     while right < len(nums):
25         if nums[right] != 0:
26             nums[left], nums[right] = nums[right], nums[left]
27             left += 1
28             right += 1
29         else:
30             right += 1
31 
32 
33 print("-------测试moveSeros()------")
34 nums = [0, 1, 0, 3, 0, 12]
35 moveZeros1(nums)
36 print(nums)
37 
38 
39 def bubbleSort(nums):
40     '''
41     冒泡排序
42     :param nums:
43     :return:
44     '''
45     n = len(nums)
46     for i in range(n):
47         for j in range(n - i - 1):
48             if nums[j] > nums[j + 1]:
49                 nums[j], nums[j + 1] = nums[j + 1], nums[j]
50 
51     return nums
52 
53 
54 print("-----测试bububleSort(nums)-------")
55 nums = [2, 1, 3, 5, 2]
56 numSort = bubbleSort(nums)
57 print(numSort)

总结：上述采用两种方法实现，方法1参考冒泡排序思想，方法2采用双指针。方法2时间复杂度低，为O(N)，方法1时间复杂度为O(N^2).顺带写出了冒泡排序。

双指针实现过程：题目要求将0移动到数组后面，保持非零元素顺序不变，将其移到前面，因此双指针实现过程中，设定两个指针，快指针和慢指针，当快指针指向元素非零时，交换快指针和慢指针值，然后将快慢指针同时向后移动；当快指针指向元素为0时，向后移动，直至移动到数组末尾，结束循环。

方法1参开冒泡排序思想，从头开始遍历数组，若元素为0，将该元素和下一个相邻元素交换，每遍历一遍，会移动一个0元素至数组末尾。