Algorithem_MoveZeros#
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
解法一#
实现逻辑：
首先把所有非 0 元素放到前面，并记录长度，最后从非 0 长度到数组尾部元素置为 0
举例如下：
nums = [1, 0, 2, 3, 0, 6]
j = 0
遍历数组：
i = 0，nums[0] = 1, != 0, num[j] = num[i], j + 1, [1, 0, 2, 3, 0, 6]
i = 1, nums[1] = 0,
i = 2, nums[2] = 2, != 0, num[j] = num[i], j + 1, [1, 2, 2, 3, 0, 6]
i = 3, nums[3] = 3, != 0, num[j] = num[i], j + 1, [1, 2, 3, 3, 0, 6]
i = 4, nums[4] = 0,
i = 5, nums[5] = 6, != 0, num[j] = num[i], j + 1, [1, 2, 3, 6, 0, 6]
// 从 j 开始到数组末尾的元素置为0
j = 4, [1, 2, 3, 6, 0, 0]
代码如下：
class Solution {
func moveZeroes(_ nums: inout [Int]) {
// 首先把所有非0的取出来
var j = 0
for i in 0..<nums.count {
if nums[i] != 0 {
// 当前元素不为0
// j从0开始
nums[j] = nums[i]
j = j + 1
}
}
// 从 j 开始到数组末尾的元素置为0
while j < nums.count {
nums[j] = 0
j = j + 1
}
}
}
解法二#
实现逻辑：
定义一个变量代表数组中 0 的个数，遍历数组，如果当前元素是 0，则变量加 1，如果当前元素不为 0 且变量长度大于 0，则交换当前元素和前面变量个元素的位置。
举例如下：
nums = [1, 0, 2, 3, 0, 6]
snowballSize = 0
遍历数组：
i = 0，nums[0] = 1, snowballSize = 0;
i = 1, nums[1] = 0, snowballSize += 1;
i = 2, nums[2] = 2, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 0, 3, 0, 6]
i = 3, nums[3] = 3, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 3, 0, 0, 6]
i = 4, nums[4] = 0, snowballSize += 1;
i = 5, nums[5] = 6, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 3, 6, 0, 0]
代码如下：
class Solution {
func moveZeroes(_ nums: inout [Int]) {
// 定义含0的长度
var snowballSize = 0
// 遍历数组
for index in 0..<nums.count {
let num = nums[index]
// 如果当前元素为0，则含0长度字段加1
if num == 0 {
snowballSize += 1
}
else if snowballSize >= 1 {
// 如果当前含0字段长度大于1，则交换当前元素和前一个元素的位置
nums.swapAt(index, index-snowballSize)
}
}
}
}