Leetcode 287 - Find the Duplicate Number

題目

Problem#

給你一個整數陣列 nums 包含 $n+1$ 個整數，值域 $[1, n]$，陣列裡面只包含一個重複的數字，找出這個重複的數字並回傳。
限制: 不能修改原本的陣列，且空間複雜度必須在 $O(1)$

• Follow up:
  • 證明陣列裡面只包含一個重複的數字的正確性?
  • 解在 $O(n)$ 時間複雜度內

測資限制#

• $1 \le n \le 10^5$
• $1 \le val \le n$

想法#

• Sol1 hashmap
  • 最直接就是使用 hashmap 去紀錄數字出現次數，如果 $>= 2$ 就是重複的數字，但不符題目要求
• Sol2 Sort
  • sort 一遍，重複的數字便會相鄰，如此一來找相鄰相同的數字即是答案
• Sol3 Encode negative
  • 因為題目有 $n+1$ 個數字，且值域是 $[1, n]$，所以如果將出現過的數字(i)用負號 encode 在 nums[i] 的話，遇到新的數字就只要先 abs(i)，然後看 nums[i] 是負的話就是有出現過
• Sol4 Floyd’s Tortoise and Hare 龜兔賽跑算法
  • 如果把 nums 陣列看成圖，也就是對於點 i 來說，它指向 nums[i]
  • 所以如果存在重複的數字的話，代表圖一定存在環，因為會有兩個數字指向同一個數字，且重複的數字就在環的開始處
  • 所以問題變成找環存不存在，找到的話找環開始的數字即可

AC Code#

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(1)$

賞析#

• 官方題解還有 binary search 的解法，但我還沒看

心得#

在寫這題的我 be like: