【题目描述】
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
【示例】
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
【说明】
1、必须在原数组上操作,不能拷贝额外的数组。
2、尽量减少操作次数。
【思路1】
1、把不为0的数字往前移,标记0的个数k,在后边添加k个0;
2、时间复杂度O(n)
3、空间复杂度O(1)
Swift代码实现
func moveZeroes(_ nums: inout [Int]) {
var k = 0
for i in 0..<nums.count {//先把不为0的数字提到前边
if nums[i] != 0 {
nums[k] = nums[i]
k+=1
}
}
for j in k..<nums.count {//后边补0
nums[j] = 0
}
}
【思路2】
1、使用一个指针变量来标记第一个0的index,遇到不为0的数字和0交换,直到交换完毕
2、时间复杂度O(n)
3、空间复杂度O(1)
4、很巧妙的!!!
Swift代码实现:
func moveZeroes(_ nums: inout [Int]) {
var k = 0//永远标识第一个0的位置,当非0位置 和 0位置交换后,k++
for i in 0..<nums.count {
if nums[i] != 0 {
if i != k {
let tmp = nums[i]
nums[i] = nums[k]
nums[k] = tmp
}
k+=1
}
}
}