Algorithem_MoveZeros#
整数配列 nums が与えられた場合、0 を配列の末尾に移動させながら非ゼロ要素の相対的な順序を維持します。
配列のコピーを作成せずに、インプレースでこれを行う必要があることに注意してください。
例 1：
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
例 2：
Input: nums = [0]
Output: [0]
解法一#
実装ロジック：
まず、すべての 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]) {
// まず、すべての0でない要素を取り出す
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 でなく、変数の長さが 1 以上の場合、現在の要素と前の変数の要素の位置を交換します。
以下は例です：
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の場合、snowballSizeを増やす
if num == 0 {
snowballSize += 1
}
else if snowballSize >= 1 {
// 現在の含0フィールドの長さが1以上の場合、現在の要素と前の要素の位置を交換する
nums.swapAt(index, index-snowballSize)
}
}
}
}