你不可不会的几种移动零的方法
前言
本文主要介绍通过「末尾补零」以及「交换零元素与非零元素」的策略来解答此题,供大家参考,希望对大家有所帮助。
移动零
解题思路
根据题意,要把数组中所有 0 移动到数组的末尾,还要保持非零元素的「相对位置」,只需要遍历一遍数组,找出「非零元素」,然后将找出的非零元素替换原数组的元素,原数组中「未替换的元素全部用零去替换」即可。
末尾补零法
「举例」
以数组 nums =[0,1,0,3,12]为例子,如下图示。
遍历整个数组,找出所有非零元素。
替换
遍历、查找和替换的完整过程,如下动图示。
「说明」
不需要全部查找完数组中的非零元素之和,再去替换,可以「边查找边替换」,这样就不需要「开辟额外空间存储查找到的非零元素」。
Show me the Code
「C」
1 void moveZeroes(int* nums, int numsSize){ 2 int j = 0; // 区间[0...j)中存放非零元素 3 for (int i = 0; i < numsSize; ++i) { 4 /* 寻找数组中所有的非零元素,并保存在区间[0...j)中 */ 5 if (nums[i] != 0) { 6 nums[j++] = nums[i]; 7 } 8 } 9 10 /* 原数组未被非零元素替换的元素全部置为0 */ 11 while (j < numsSize) { 12 nums[j++] = 0; 13 } 14 }
View Code
「C++」
1 void moveZeroes(vector<int>& nums) { 2 int j = 0; 3 for (int i = 0; i < nums.size(); i++) { 4 if (nums[i] != 0) { 5 nums[j++] = nums[i]; 6 } 7 } 8 9 while (j < nums.size()) { 10 nums[j++] = 0; 11 } 12 }
View Code
「Python3」
1 def moveZeroes(self, nums): 2 j, length = 0, len(nums) 3 for i in range(length): 4 if nums[i] != 0: 5 nums[j] = nums[i] 6 j += 1 7 while j < length: 8 nums[j] = 0 9 j += 1
View Code
「Golang」
1 func moveZeroes(nums []int) { 2 j, length := 0, len(nums) 3 for i := 0; i < length; i++ { 4 if nums[i] != 0 { 5 nums[j] = nums[i] 6 j++ 7 } 8 } 9 10 for j < length { 11 nums[j] = 0 12 j++ 13 } 14 }
View Code
「复杂度分析」
时间复杂度:「O(n)」,其中 n 是数组的长度,需要遍历一遍数组。
空间复杂度:「O(1)」,未开辟额外的存储空间。
交换法
由于题目的说明中要求「尽量减少操作次数」,因此可以考虑通过「遍历查找到非零元素,再交换非零元素与当前数组的第一个零元素」的策略,来减少方法一种的补零操作,从而减少操作次数。
「举例」
还是以数组 nums =[0,1,0,3,12]为例子,其交换过程如下图示。
由于 nums[1] 为非零元素,nums[0] 为零元素,因此交换它们。
其完整查找和交换过程,如下动图示。
Show me the Code
「C++」
1 void moveZeroes(vector<int>& nums) { 2 for (int i = 0, k = 0; i < nums.size(); i++) { 3 if (nums[i] != 0) { 4 if (i != k) { 5 swap(nums[k++], nums[i]); 6 } else { 7 k++; 8 } 9 } 10 } 11 }
View Code
「Python3」
1 def moveZeroes(self, nums: List[int]) -> None: 2 k, length = 0, len(nums) 3 for i in range(length): 4 if nums[i] != 0: 5 if i != k: 6 nums[k], nums[i] = nums[i], nums[k] 7 k += 1 8 else: 9 k += 1
View Code
「Golang」
1 func moveZeroes(nums []int) { 2 k, length := 0, len(nums) 3 for i := 0; i < length; i++ { 4 if nums[i] != 0 { 5 if i != k { 6 nums[k], nums[i] = nums[i], nums[k] 7 k++ 8 } else { 9 k++ 10 } 11 } 12 } 13 }
View Code
「说明」
上述的代码中都加了「i 是否等于 k」的判断,这是因为如果数组中的元素都是「非零元素」,就不需要「自己与自己交换」,也算是一个小的优化。
「复杂度分析」
时间复杂度:「O(n)」,其中 n 是数组的长度,需要遍历一遍数组。
空间复杂度:「O(1)」,未开辟额外的存储空间。