283. 移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
一、暴力解法
直观而言,依然是采用双指针解法,i 用于遍历整个 nums 数组,j 则基于 i 进行获取不等于 0 的索引,并通过临时变量进行替换 i 和 j 的数字。
代码如下:
fun moveZeroes(nums: IntArray): Unit {
if (nums.isEmpty()) {
return
}
for (i in nums.indices) {
if (nums[i] == 0) {
for (j in i until nums.size) {
if (nums[j] != 0) {
var tempNum = nums[i]
nums[i] = nums[j]
nums[j] = tempNum
break
}
}
}
}
}
执行消耗:
二、偷梁换柱法
在网上看到一种解法很 nice,大概思路如下:
当然,我的描述可能有点问题,具体看代码:
fun moveZeroes1(nums: IntArray): Unit {
if (nums.isEmpty()) {
return
}
var j = 0
for(i in nums.indices){
if(nums[i] != 0){
nums[j++] = nums[i]
}
}
while (j < nums.size){
nums[j++] = 0
}
}
执行消耗:
下面附上目前 LeetCode 推荐范例,以供大家学习参考。
执行用时为 204 ms 的范例
fun moveZeroes(nums: IntArray): Unit {
var pointA = 0
var pointB = 0
while (pointB < nums.size) {
val numB = nums[pointB]
if (numB != 0) {
nums[pointB] = nums[pointA]
nums[pointA] = numB
pointA++
}
pointB++
}
}
执行消耗内存为 35048 kb 的范例
fun moveZeroes(nums: IntArray): Unit {
var a = 0
var b = 0
while (b < nums.size) {
if (nums[b] != 0) {
nums[a] = nums[b]
if (b > a) {
nums[b] = 0
}
a++
}
b++
}
}