【LeetCode】26. Remove Duplicates from Sorted Array に挑戦！！

問題

整数配列 nums が非減少順にソートされているとき、重複をその場で削除して、各ユニークな要素が1回だけ現れるようにしてください。要素の相対的な順序は維持する必要があります。その後、nums におけるユニークな要素の数を返します。
nums のユニークな要素数を k とします。解答が受け入れられるには、次のことを満たす必要があります：配列 nums を変更し、最初の k 個の要素に nums に最初から存在していた順番でユニークな要素を格納します。nums の残りの部分やサイズは重要ではありません。k を返します。

例 1：
入力: nums = [1,1,2]
出力: 2, nums = [1,2,_]
説明:
関数は k = 2 を返し、nums の最初の2つの要素がそれぞれ 1 と 2 になります。それ以降の部分は無視して構いません（したがってアンダースコアで表記）。

例 2：
入力: nums = [0,0,1,1,1,2,2,3,3,4]
出力: 5, nums = [0,1,2,3,4,_,_,_,_,_]
説明:
関数は k = 5 を返し、nums の最初の5つの要素がそれぞれ 0, 1, 2, 3, 4 になります。それ以降の部分は無視して構いません。

制約

1 <= nums.length <= 30,000
-100 <= nums[i] <= 100
nums は非減少順にソートされている。

実験（取っ掛かり）

例えば、下記のような配列を考えてみましょう。

nums = [0,0,1,1,1,2,2]

左側から視線を右側に移していき、重複を削除し、左側に詰める。（人がやるとなんて簡単なんでしょう！！）
要素は3つなので、k=3となる。

ここで重複する数とは何かを考えてみましょう。

重複する数
⇔ 前回と現在が同じ数

この言い換えはピンときますでしょうか？
プログラムで左から処理する場合は、nums[0]から始まります。
この段階では、nums[1]以降は見えていません。

ポインターを右側に1つずらして初めてnums[1]の値が見えます。
この段階で、nums[0]は0でnums[1]は0のため数が重複しているということがプログラムでわかります。

さらに右側に1つずらします。

このときどのような操作をしたいかというと、重複している数を削除し、左側に詰めたいわけです。

もう少しだけ実験しましょう。
0が4つ続いている場合はどうでしょうか？
先程と同じ場所（ピンク色の部分）を1で上書きをしています。

2つの具体例を抽象化すると、ピンク色の部分を特定し、前回とは別の数が出てきた場合にその数でピンク色の部分に上書きをしてあげれば良さそうですね。

slowポインターとfastポインターという考え方

slowポインターは遅く動き、fastポインターは早く動く。

役割としてそれぞれ、
・slowポインターは文字を保存する場所を指す
・fastポインターは1つずつどんどん進んでいき、現在の場所を指す

「保」は保存の意味。
配列の上側にslowポインター（保）
配列の下側にfastポインター

fastポインターはどんどん進んでいく

解法（思考プロセス）

方針：ピンク色の部分を特定し、前回と別の数の場合はその数でピンク色の部分に上書きをする
　　　※ピンク色の部分：保存場所

ピンク色の部分を指し示すポインター
→　slowポインター

現在の位置を指し示すポインター
→ fastポインター

では、配列の何番目から考えていくのがいいのでしょうか？
最初からnums[0]から見ていった方がいいのでしょうか？

今回は重複する数を削除するというのが目的です。
最初から見ていった場合、nums[0]の時点で重複の数があるかどうかは判断できますか？
答えはノーですね。（現時点では確認できる要素は1つのため。）

nums[1]から見ないと重複の数があるかどうかは判断できません。

ですので、初期の状態はこのようになります。
例によって、上側にslowポインター（保存の「保」）、下側にfastポインターを配置します。

初期の時点で0が重複しているので、ピンク色の部分は確定しました。
次に「前回と別の数」を検索していきましょう。

fastポインターを右側に1つずらしました。
前回(0)と別の数(1)が出ましたね。

ピンク色の部分にその別の数で上書き。

別の数で上書きしていて保存しているので、slowポインター（保）を右側にずらす（次の保存場所）
これが一連のアルゴリズムの流れになります。

続きになります。

あともう少し。
fastポインターを右側にずらす。
要素全てを走査できたので終了になります。

回答でほしい配列は下記の通りです。
slowポインターの手前までの要素になります。

解法（実装）

※実際のLeetCodeはremoveDuplicates関数のみの提出になります。
　main関数は自分で実行して確認するためのものになります。

package main

import "fmt"

func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	// slowポインター:保存場所を指す
	// 1番目から開始
	slow := 1

	// fastポインター：現在の場所を指す。一つずつ走査する
	// 1番目から開始
	for fast := 1; fast < len(nums); fast++ {
		// 前回とは別の数が出てきた場合、nums[slow]（ピンク色の部分）にいれる
		// nums[slow]に保存した後は、slowを右側にずらす
		if nums[fast] != nums[fast-1] {
			nums[slow] = nums[fast]
			slow++
		}
	}

	return slow
}

func main() {
	nums := []int{0, 0, 1, 1, 1, 2, 2}

	k := removeDuplicates(nums)

	// 結果の出力
	fmt.Printf("Unique count: %d\n", k)
	fmt.Printf("Updated nums: %v\n", nums[:k])
}

main.go 実行結果

Unique count: 3
Updated nums: [0 1 2]