LeetCode 283. 移动零 - easy
LeetCode 283. 移动零 - easy
贺biubiu
发布于 2020-12-14 11:08:09
发布于 2020-12-14 11:08:09
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，大概思路如下：
- 依然基于双指针，i 负责遍历整个 nums 数组；j 负责将不等于 0 的值塞到当前 nums[j] 的位置。随后将 j 到 nums.size 期间数字变更为 0 即可。
当然，我的描述可能有点问题，具体看代码：
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++
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-12-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读