いいものをつくろう

CTOの日記

アルゴリズム

leetcode medium find all duplicate element in array 難しい

投稿日:

みなさま、目標に近づいてますでしょうか?

おはようございます。

今回も難しかったです。

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]

とここまで来て

やはり

数字は1以上にならないとマズイことに気がつきました

なぜなら0だけ符号を反転できないからです

ということで

A = [ 1, 3,  4, 3,  5]

というとにします。

改めまして、これを最初の要領で処理すると

A = [ -1, 3,  4, 3,  5]

という形に表します

これで

インデックス1はもう見たぜ、つまりは数字の1はもう見たぜという

ことを記憶できす。

ここでのポイントはO(1)のスペースで解けと言われたら どうにか既存のスペースをmutateしてデータを記憶できないか?と考えます 特に正の数などの制約があれば負の数に判定しても性質が変わらないことを 利用できないか?

と考えることができるはずです

続きます。次index 1で3ですね。ポジティブでしたので問題なしです

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 ということになります。

で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で、3はもう見た、ということになります。

なので3を答えとして追加します

隠れメッセージはもう入っているので

次、最後ですね。

A = [ -1, 3,  -4, -3,  5]

index 4になります5ですね。A[abs(5-1)]は5で正なので初めてですね。

入れこれで以上

A = [ -1, 3,  -4, -3,  -5]

ループを抜けるので答えは ans = [3]ということになります

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.