题目
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
- 输入:
nums = [0,1,0,3,12]
- 输出:
[1,3,12,0,0]
示例 2:
- 输入:
nums = [0]
- 输出:
[0]
方法一:双指针
思路及解法
使用双指针,左指针指向当前已经处理好的序列的尾部,右指针指向待处理序列的头部。
右指针不断向右移动,每次右指针指向非零数,则将左右指针对应的数交换,同时左指针右移。
注意到以下性质:
左指针左边均为非零数;
右指针左边直到左指针处均为零。
因此每次交换,都是将左指针的零与右指针的非零数交换,且非零数的相对顺序并未改变。
代码
class Solution {
func moveZeroes(_ nums: inout [Int]) {
let n: Int = nums.count
var left: Int = 0
var right: Int = 0
while right < n {
if 0 != nums[right] {
nums.swapAt(left, right)
left += 1
}
right += 1
}
}
}
复杂度分析
时间复杂度:,其中 为序列长度。每个位置至多被遍历两次。
空间复杂度:。只需要常数的空间存放若干变量。
方法二:两次遍历
思路及解法
我们创建两个指针 i
和 j
,第一次遍历的时候指针j用来记录当前有多少非 0
元素。即遍历的时候每遇到一个非 0
元素就将其往数组左边挪,第一次遍历完后,j
指针的下标就指向了最后一个非 0
元素下标。
第二次遍历的时候,起始位置就从 j
开始到结束,将剩下的这段区域内的元素全部置为 0
。
代码
class Solution {
func moveZeroes(_ nums: inout [Int]) {
let n: Int = nums.count
var j = 0
for i in 0..<n {
if 0 != nums[i] {
nums[j] = nums[i]
j += 1
}
}
for i in j..<n {
nums[i] = 0
}
}
}
复杂度分析
时间复杂度:,其中 为序列长度。
空间复杂度:。
方法三:一次遍历
思路及解法
这里参考了快速排序的思想,快速排序首先要确定一个待分割的元素做中间点 x
,然后把所有小于等于 x
的元素放到 x
的左边,大于 x
的元素放到其右边。
这里我们可以用 0
当做这个中间点,把不等于 0
(注意题目没说不能有负数)的放到中间点的左边,等于 0
的放到其右边。
这的中间点就是 0
本身,所以实现起来比快速排序简单很多,我们使用两个指针 i
和 j
,只要 0 != nums[i]
,我们就交换 nums[i]
和 nums[j]
。
代码
class Solution {
func moveZeroes(_ nums: inout [Int]) {
let n: Int = nums.count
var j = 0
for i in 0..<n {
if 0 != nums[i] {
nums[j] = nums[i]
j += 1
}
}
for i in j..<n {
nums[i] = 0
}
}
}
复杂度分析
时间复杂度:,其中 为序列长度。
空间复杂度:。