初级算法-数组-移动零
2021-08-02 本文已影响0人
coenen
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
说明:
必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。
摘一个示例做个说明.
示例 1:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
条件分析:
- 保持非零相对位置 -> 不能更改数组非0顺序
- 原数组操作
- 尽量减少操作次数 -> 减少循环
解决思路1:
- 根据分析1、2,说明需要在原数组中进行数据移动
- 根据分析3,尽量减少循环次数
从后往前循环判断,如果为0,则删除该数据,并在数组末尾加0
解决思路2:
1.根据分析1、2,采用双指针,不是0的往前挪,
利用双指针,进行循环判断,不是0,则赋值到最前位置的指针,然后指针右移,最后循环指针后的内容置0
解决思路3:对思路2优化,做临时变量,然后交换
代码实现-Swift版本:
思路1代码:
func moveZeroes(_ nums: inout [Int]) {
// 从后往前判断,如果有0,则挪到最后,并且删除该位置0
for i in 0 ..< nums.count {
if nums[nums.count - 1 - i] == 0 {
nums.remove(at: nums.count - 1 - i)
nums.append(0)
}
}
}
移动零 删除操作 提交结果.jpg
思路2代码:
func moveZeroes(_ nums: inout [Int]) {
// 双指针,不是0的往前,然后剩下的全0
var index = 0
for i in 0 ..< nums.count {
if nums[i] != 0 {
nums[index] = nums[i]
index += 1
}
}
for i in index ..< nums.count {
nums[i] = 0
}
}
思路3代码:
func moveZeroes(_ nums: inout [Int]) {
/**
双指针,不是0的往前,然后剩下的全0
时间36ms, 90.96% 内存14.1MB, 67.8%
*/
var index = 0
for i in 0 ..< nums.count {
if nums[i] != 0 {
let tmp = nums[index]
nums[index] = nums[i]
nums[i] = tmp
index += 1
}
}
}
代码优化
func moveZeroes(_ nums: inout [Int]) {
var index = 0
for i in 0 ..< nums.count {
if nums[i] != 0 {
nums.swapAt(index, i)
index += 1
}
}
}
移动零 双指针 提交结果.jpg
测试用例:
var array1 = [2,0,0,1,0,9,9]
考察要点:
- 数组
- 双指针