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]是負的話就是有出現過
- 因為題目有 $n+1$ 個數字，且值域是 $[1, n]$，所以如果將出現過的數字(
- Sol4 Floyd’s Tortoise and Hare 龜兔賽跑算法
- 如果把
nums陣列看成圖，也就是對於點i來說，它指向nums[i] - 所以如果存在重複的數字的話，代表圖一定存在環，因為會有兩個數字指向同一個數字，且重複的數字就在環的開始處
- 所以問題變成找環存不存在，找到的話找環開始的數字即可
- 如果把
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(1)$
賞析#
- 官方題解還有 binary search 的解法，但我還沒看
心得#
在寫這題的我 be like: