题目:
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作,不能拷贝额外的数组。
- 尽量减少操作次数。
解题思路:双重for循环,类似冒泡排序:找到零,和后面的数字依次交换。
func moveZeroes(nums []int) {
count:=0
for i:=0;i
if nums[i]==0{
for j:=i+1;j
nums[j-1],nums[j]=nums[j],nums[j-1]
}
count++
}else{
i++
}
}
}
运行时间132ms
代码优化:
func moveZeroes(nums []int) {
length:=len(nums)
if length<2{
return
}
for i:=0;i
if nums[i]==0{
for j:=i+1;j
nums[j-1]=nums[j]
}
nums[length-1]=0
length--
}else{
i++
}
}
}
运行时间100ms
再优化:反向思维,考虑将非零数据依次放到数组中,后面则全为0
func moveZeroes(nums []int) {
k:=0
for i:=0;i
if nums[i]!=0{
if k!=i{
nums[k]=nums[i]
}
k++
}
}
for k
nums[k]=0
k++
}
}
运行时间88ms