| 程序员小熊 责编 | 欧阳姝黎

前言

今天给大家带来一道与数组相关得题目，这道题同时也是脸书和彭博得面试题，即力扣上得第283题-移动零。

感谢介绍通过「末尾补零」以及「交换零元素与非零元素」得策略来解答此题，供大家参考，希望对大家有所帮助。

移动零

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


示例:

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

说明:

1、必须在原数组上操作，不能拷贝额外得数组。
2、尽量减少操作次数。
解题思路

根据题意，要想把数组中所有 0 移动到数组得末尾，还要保持非零元素得「相对位置」，只需要遍历一遍数组，找出「非零元素」，然后将找出得非零元素替换原数组得元素，原数组中「未替换得元素全部用零去替换」即可。

末尾补零法

「举例」

以数组nums =[0,1,0,3,12]为例，如下图示。

示例

遍历整个数组，找出所有非零元素。

找出所有非零元素

替换

替换

遍历、查找和替换得完整过程，如下动图示。

「说明」

不需要查找完数组中得非零元素之和，再替换，可以「边查找边替换」，这样就不需要「开辟额外空间存储查找到得非零元素」。

Show me the Code

「C」

void moveZeroes(int* nums, int numsSize){
int j = 0; // 区间[0...j)中存放非零元素
for (int i = 0; i < numsSize; ++i) {

if (nums[i] != 0) {
nums[j++] = nums[i];
}
}


while (j < numsSize) {
nums[j++] = 0;
}
}


「C++」

void moveZeroes(vector<int>& nums) {
int j = 0;
for (int i = 0; i < nums.size; i++) {
if (nums[i] != 0) {
nums[j++] = nums[i];
}
}

while (j < nums.size) {
nums[j++] = 0;
}
}


「Python3」

def moveZeroes(self, nums):
j, length = 0, len(nums)
for i in range(length):
if nums[i] != 0:
nums[j] = nums[i]
j += 1
while j < length:
nums[j] = 0
j += 1


「Golang」

func moveZeroes(nums []int) {
j, length := 0, len(nums)
for i := 0; i < length; i++ {
if nums[i] != 0 {
nums[j] = nums[i]
j++
}
}

for j < length {
nums[j] = 0
j++
}
}


「复杂度分析」

时间复杂度：「O(n)」，其中n是数组得长度，需要遍历一遍数组。

空间复杂度：「O(1)」，未开辟额外得存储空间。

交换法

由于题目得说明中要求尽量减少操作次数，因此可以通过「遍历查找到非零元素，再交换非零元素与当前数组得第壹个零元素」得策略，来减少方法一种得补零操作，从而减少操作次数。

「举例」

还是以数组 nums =[0,1,0,3,12]为例子，其交换过程如下图示。

由于 nums[1] 为非零元素，nums[0] 为零元素，因此交换它们。

其完整查找和交换过程，如下动图示。

Show me the Code

「C++」

void moveZeroes(vector<int>& nums) {
for (int i = 0, k = 0; i < nums.size; i++) {
if (nums[i] != 0) {
if (i != k) {
swap(nums[k++], nums[i]);
} else {
k++;
}
}
}
}


「Python3」

def moveZeroes(self, nums: List[int]) -> None:
k, length = 0, len(nums)
for i in range(length):
if nums[i] != 0:
if i != k:
nums[k], nums[i] = nums[i], nums[k]
k += 1
else:
k += 1


「Golang」

func moveZeroes(nums []int) {
k, length := 0, len(nums)
for i := 0; i < length; i++ {
if nums[i] != 0 {
if i != k {
nums[k], nums[i] = nums[i], nums[k]
k++
} else {
k++
}
}
}
}


「说明」

上述得代码中都加了「i 是否等于 k」得判断，这是因为如果数组中得元素都是「非零元素」，就不需要「自己与自己交换」，也算是一个小得优化。

「复杂度分析」

时间复杂度：「O(n)」，其中n是数组得长度，需要遍历一遍数组。

空间复杂度：「O(1)」，未开辟额外得存储空间。