sosodemonai https://blog.hatena.ne.jp/sosodemonai/ Neunomizuの日記 https://propyon.hateblo.jp/ leetcode tags: leetcode 問題 Explore Problems アイデア 要素数がn + 1の整数の配列が与えられた時，要素は[1, n]であり，鳩の巣原理より少なくとも1つの要素は重複しています． このうち，重複している要素を探せというもの． 注意点は 配列を操作してはいけない． つまりstd::sortは使えない． 空間計算量は$O(1)$しか許されていない． つまり新たなデータ構造が使えない． 時間計算量は$O(n^{2})$よりも小さい必要がある． つまり2重ループも使えない． 1つしか重複した数はないが，それは1つ以上重複している可能性がある． 解法 この問題ではcycle d… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpropyon.hateblo.jp%2Fentry%2F2020%2F02%2F13%2F175628" title="# LeetCode Medium 287. Find the Duplicate Number - Neunomizuの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://i.imgur.com/rIQmDYC.png Hatena Blog https://hatena.blog 2020-02-13 17:56:28 rich https://propyon.hateblo.jp/entry/2020/02/13/175628 1.0 100%