Algorithem_MoveZeros#
整数配列 nums が与えられたとき、すべての 0 を配列の末尾に移動し、非ゼロ要素の相対的な順序を維持します。
配列のコピーを作成せずに、これをインプレースで行う必要があることに注意してください。
例 1:
入力: nums = [0,1,0,3,12]
出力: [1,3,12,0,0]
例 2:
入力: nums = [0]
出力: [0]
解法一#
実装ロジック：
まず、すべての非ゼロ要素を前に置き、長さを記録し、最後に非ゼロの長さから配列の末尾の要素を 0 に設定します。
以下の例を示します：
nums = [1, 0, 2, 3, 0, 6]
j = 0
配列を遍歴：
i = 0，nums[0] = 1, != 0, num[j] = num[i], j + 1, [1, 0, 2, 3, 0, 6]
i = 1, nums[1] = 0,
i = 2, nums[2] = 2, != 0, num[j] = num[i], j + 1, [1, 2, 2, 3, 0, 6]
i = 3, nums[3] = 3, != 0, num[j] = num[i], j + 1, [1, 2, 3, 3, 0, 6]
i = 4, nums[4] = 0,
i = 5, nums[5] = 6, != 0, num[j] = num[i], j + 1, [1, 2, 3, 6, 0, 6]
// j から配列の末尾までの要素を 0 に設定
j = 4, [1, 2, 3, 6, 0, 0]
コードは以下の通りです：
class Solution {
func moveZeroes(_ nums: inout [Int]) {
// まずすべての非ゼロを取り出す
var j = 0
for i in 0..<nums.count {
if nums[i] != 0 {
// 現在の要素が 0 でない
// j は 0 から始まる
nums[j] = nums[i]
j = j + 1
}
}
// j から配列の末尾までの要素を 0 に設定
while j < nums.count {
nums[j] = 0
j = j + 1
}
}
}
解法二#
実装ロジック：
配列中の 0 の個数を表す変数を定義し、配列を遍歴します。現在の要素が 0 の場合、変数を 1 増やし、現在の要素が 0 でなく、変数の長さが 0 より大きい場合、現在の要素と前の変数の個数の要素の位置を交換します。
以下の例を示します：
nums = [1, 0, 2, 3, 0, 6]
snowballSize = 0
配列を遍歴：
i = 0，nums[0] = 1, snowballSize = 0;
i = 1, nums[1] = 0, snowballSize += 1;
i = 2, nums[2] = 2, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 0, 3, 0, 6]
i = 3, nums[3] = 3, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 3, 0, 0, 6]
i = 4, nums[4] = 0, snowballSize += 1;
i = 5, nums[5] = 6, snowballSize > 0, swap(i, i - snowballSize), [1, 2, 3, 6, 0, 0]
コードは以下の通りです：
class Solution {
func moveZeroes(_ nums: inout [Int]) {
// 含まれる 0 の長さを定義
var snowballSize = 0
// 配列を遍歴
for index in 0..<nums.count {
let num = nums[index]
// 現在の要素が 0 の場合、含まれる 0 の長さを 1 増やす
if num == 0 {
snowballSize += 1
}
else if snowballSize >= 1 {
// 現在の含まれる 0 の長さが 1 より大きい場合、現在の要素と前の要素の位置を交換
nums.swapAt(index, index-snowballSize)
}
}
}
}