どーも！
たかぽんです！
またまた日付変わってしまいましたが...
今日もやったので書いていきます！！
448. Find All Numbers Disappeared in an Array
今回の問題はこちらです。
こちらの問題は、最初に与えられたリストの中に、数値のデータが入っているのですが、本来はその長さに対応した値がそれぞれ要素に入っているようです。
たとえば...
[1,2,3,4,5]といった配列です。この配列の中身から、一部の要素が消えたり、重複することによって、含まれていない文字があるとします。
その文字の一覧をリストとして返せという感じです。
例えば[1,3,3,4,4]の場合、配列の長さは5です。
そのため、本来あるべき姿は[1,2,3,4,5]のため、今回はそれに存在していない[2,5]を返せばいいわけです。
なんとなく問題がわかったところで、アルゴリズムをかんがようと思います！
アルゴリズム
方法としては、元々の配列の長さ分forを回し、その際のincrementをそのまま値として、含まれていない場合のみ別の配列に書き出す...といった形でできそうです。
イメージだと以下です。
inputが[1,3,3,4,4]の場合...
配列の長さは5なので、forを5回す。(ただし、今回、配列には0は含まれないため、iの初期値は1）
i = 1のとき...
inputのset（重複を除いた物）に1が含まれるかどうか確認。
今回は1,3,4になるため、含まれている。
その場合は何もしない。
i = 2のとき...
2が含まれるかどうか確認。
1,3,4には含まれないため、この値は消えた値(Disappeared Numbersの一つ）。
別途、出力ようの配列に追加
i = 3のとき...
...
なんとなくつかめたでしょうか・・・？
リストには0という値は存在しないため、forのrangeのデフォルトの0からスタートではなく、1からスタートしないといけない...等はありますが、難しくはないと思います。
では、最後にpythonで書いた場合のコードを記載しておきます。
あらかじめ、検索対象は重複を削除している（set(nums))点、rangeで初期値を1からにしている点、それによってループ回数が減らないように、lenに+1している点あたり理解できればなんてことないと思います！
setを使わずともおそらく可能だと思いますが、気持ち処理が早くなったりするんじゃないかなぁ...?とか思いを込めてsetしてます...!w
提出したコード
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
setNums = set(nums)
output = []
for i in range(1, len(nums)+1):
print(i)
if i not in setNums:
output.append(i)
return output
# 結果
Runtime: 404 ms, faster than 23.61% of Python3 online submissions for Find All Numbers Disappeared in an Array.
Memory Usage: 24.2 MB, less than 30.23% of Python3 online submissions for Find All Numbers Disappeared in an Array.