みなさま、目標に近づいてますでしょうか？
おはようございます。
今回も難しかったです。
midiumは難しですね。
頭の体操で算数というかatcoderチックな問題だとも思いました
こちらの問題
find-all-duplicates-in-an-array
最初頑張って考えるんですが
どうしてもスペースを使ってしまったら
ソートしてからだとO(nlogn)のスピードになってしまうし
結構お手上げだったんです。
一応ヒントとして
要素の持ちうる範囲は配列数以下である 1 <= A[i] < n
という制約があるのですが、
これが最大のヒントです
それでも考えるのですが、結局自力では
回答がおもつきませんでした。
geeksforgeeks.org の解説を見て
ようやく合点が言った次第です。
N = 5
A = [ 0, 2, 3, 2, 4]
という例を考えましょう
最初に0を見たときに
A[0] は0 ですと。じゃあ0のインデックスのところをマイナスにしときましょう。
インデックスというっても、俺はもうこの数字は見たよ。ということになります。
ただし元々収まっているデータは消したらダメなので符号を反対にだけさせてもらいますー
という戦法です
つまりこうなります
A = [ -0, 2, 3, 2, 4]
とここまで来て
やはり
数字は１以上にならないとマズイことに気がつきました
なぜなら０だけ符号を反転できないからです
ということで
A = [ 1, 3, 4, 3, 5]
というとにします。
改めまして、これを最初の要領で処理すると
A = [ -1, 3, 4, 3, 5]
という形に表します
これで
インデックス１はもう見たぜ、つまりは数字の１はもう見たぜという
ことを記憶できす。
ここでのポイントはO(1)のスペースで解けと言われたら どうにか既存のスペースをmutateしてデータを記憶できないか？と考えます 特に正の数などの制約があれば負の数に判定しても性質が変わらないことを 利用できないか？
と考えることができるはずです
続きます。次index 1で３ですね。ポジティブでしたので問題なしです
A = [ -1, 3, 4, 3, 5]
そしてネガティブに直します
A = [ -1, 3, -4, 3, 5]
index 2 = (3-1)を反転させました。index 2 = (3-1)つまりは3はもう見たぜという隠れ
メッセージです
次
index 2で4ですね、ポジディブですね
A = [ -1, 3, -4, 3, 5]
これは言い忘れましたが最初は絶対数で確認するので
index 2はabs(-4)で4 ということになります。
で４はすでに存在したかを知るために A[4-1]の数字か正かを見ます。この場合A[4-1] は3ですね
なのでOKです
そしてマークします。俺は四をもう見たんだという、隠れメッセージを
A = [ -1, 3, -4, -3, 5]
という形で入れます
次、index 3の数字は -3 ですね。A[abs(-3)-1]は-4ですね。
ウォーーー、これはあたりです。今まで認めてきた隠れメッセージが役に立つ時がきました
indexの数字は３で、３はもう見た、ということになります。
なので3を答えとして追加します
隠れメッセージはもう入っているので
次、最後ですね。
A = [ -1, 3, -4, -3, 5]
index 4になります5ですね。A[abs(5-1)]は５で正なので初めてですね。
入れこれで以上
A = [ -1, 3, -4, -3, -5]
ループを抜けるので答えは ans = [3]ということになります
以上です