題目
給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序贯溅。
請注意冠胯，必須在不復(fù)制數(shù)組的情況下原地對數(shù)組進(jìn)行操作火诸。
示例 1：
- 輸入：
nums = [0,1,0,3,12]- 輸出：
[1,3,12,0,0]
示例 2：
- 輸入：
nums = [0]- 輸出：
[0]
方法一：雙指針
思路及解法
使用雙指針，左指針指向當(dāng)前已經(jīng)處理好的序列的尾部荠察，右指針指向待處理序列的頭部置蜀。
右指針不斷向右移動奈搜，每次右指針指向非零數(shù)，則將左右指針對應(yīng)的數(shù)交換盯荤，同時左指針右移馋吗。
注意到以下性質(zhì)：
左指針左邊均為非零數(shù)；
右指針左邊直到左指針處均為零秋秤。
因此每次交換宏粤，都是將左指針的零與右指針的非零數(shù)交換，且非零數(shù)的相對順序并未改變灼卢。
代碼
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
}
}
}
復(fù)雜度分析
時間復(fù)雜度：
绍哎，其中
為序列長度。每個位置至多被遍歷兩次鞋真。
空間復(fù)雜度：
崇堰。只需要常數(shù)的空間存放若干變量。
方法二：兩次遍歷
思路及解法
我們創(chuàng)建兩個指針 i 和 j涩咖，第一次遍歷的時候指針j用來記錄當(dāng)前有多少非 0 元素海诲。即遍歷的時候每遇到一個非 0 元素就將其往數(shù)組左邊挪，第一次遍歷完后檩互，j 指針的下標(biāo)就指向了最后一個非 0 元素下標(biāo)特幔。
第二次遍歷的時候，起始位置就從 j 開始到結(jié)束盾似，將剩下的這段區(qū)域內(nèi)的元素全部置為 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
}
}
}
復(fù)雜度分析
時間復(fù)雜度：
空間復(fù)雜度：
方法三：一次遍歷
思路及解法
這里參考了快速排序的思想，快速排序首先要確定一個待分割的元素做中間點(diǎn) x告抄，然后把所有小于等于 x 的元素放到 x 的左邊撰茎，大于 x 的元素放到其右邊。
這里我們可以用 0 當(dāng)做這個中間點(diǎn)打洼，把不等于 0（注意題目沒說不能有負(fù)數(shù)）的放到中間點(diǎn)的左邊龄糊，等于 0 的放到其右邊。
這的中間點(diǎn)就是 0 本身募疮，所以實(shí)現(xiàn)起來比快速排序簡單很多炫惩，我們使用兩個指針 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
}
}
}
復(fù)雜度分析
時間復(fù)雜度：
空間復(fù)雜度：
