你不可不会的几种移动零的方法
前言
今天给大家带来一道与数组相关的题目，这道题同时也是脸书和彭博的面试题，即力扣上的第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) {
/* 寻找数组中所有的非零元素，并保存在区间[0...j)中 */
if (nums[i] != 0) {
nums[j++] = nums[i];
}
}
/* 原数组未被非零元素替换的元素全部置为0 */
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)」，未开辟额外的存储空间。
☞2 年增长 1 万亿！继苹果之后，微软市值也突破 2 万亿美元
[广告]赞助链接：
关注数据与安全，洞悉企业级服务市场：https://www.ijiandao.com/
让资讯触达的更精准有趣：https://www.0xu.cn/
关注KnowSafe微信公众号随时掌握互联网精彩
