題目敘述
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Constraints:
1 <= n <= 105nums.length == n + 11 <= nums[i] <= n- All the integers in
nums appear only once except for precisely one integer which appears two or more times.
Follow up:
- How can we prove that at least one duplicate number must exist in
nums?
- Can you solve the problem in linear runtime complexity?
題目翻譯
給定一個整數陣列 nums，其中的元素只有一個整數值是會重複的(且可以重複一次以上)。請在沒有修改 nums 的情況下解出這問題。其中 nums 的元素的範圍只會在 [1, n] 中，而n 是 nums 的長度。
解法解析
這題有許多的解法，雖然官方給了相當多的解法，有提到說前四種解法並不符合題目的需求，就是違反了 不修改 nums 的原則。像是 Sort 和 Negative Marking 的解法，但還是提出來是因為在面試時是個快速的解題方式。
看過各種程式語言的解法，大部分會採用以下幾種：Set, Hash Map, Floyd's Tortoise and Hare。以下的解法範例中 Go、PHP、Rust 就是使用了 Floyd's Tortoise and Hare 的解法，其他語言則是使用了 Set 的解法。因為 Floyd's Tortoise and Hare 的解法是在符合題目條件下，其時間複雜度最佳的解法。
一開始不是很懂為什麼可以用 Floyd's Tortoise and Hare 的解法，為什麼可以變成一個循環？後來看到條件是 [1, n] 才搞懂。因為這個條件，所以每個元素可以相對應彼此的 index，而不會超出 index 範圍。[1, 3, 2, 4, 5, 2] => n = 6。而重複的元素就會是循環的起始點，所以剛好就符合 Floyd's Tortoise and Hare 的情境
解法範例
Go
func findDuplicate(nums []int) int {
tortoise := nums[0]
hare := nums[0]
for {
tortoise = nums[tortoise]
hare = nums[nums[hare]]
if tortoise == hare {
break
}
}
tortoise = nums[0]
for tortoise != hare {
tortoise = nums[tortoise]
hare = nums[hare]
}
return hare
}
JavaScript
var findDuplicate = function (nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return num;
}
seen.add(num);
}
};
Kotlin
class Solution {
fun findDuplicate(nums: IntArray): Int {
val seen: MutableSet<Int> = mutableSetOf()
for (num in nums) {
if (seen.contains(num)) {
return num
}
seen.add(num)
}
return -1
}
}
PHP
class Solution
{
function findDuplicate($nums)
{
$tortoise = $hare = $nums[0];
while (true) {
$tortoise = $nums[$tortoise];
$hare = $nums[$nums[$hare]];
if ($tortoise == $hare) {
break;
}
}
$tortoise = $nums[0];
while ($tortoise != $hare) {
$tortoise = $nums[$tortoise];
$hare = $nums[$hare];
}
return $hare;
}
}
Python
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
Rust
impl Solution {
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let mut tortoise = nums[0];
let mut hare = nums[nums[0] as usize];
while tortoise != hare {
tortoise = nums[tortoise as usize];
hare = nums[nums[hare as usize] as usize];
}
tortoise = 0;
while tortoise != hare {
tortoise = nums[tortoise as usize];
hare = nums[hare as usize];
}
tortoise
}
}
Swift
class Solution {
func findDuplicate(_ nums: [Int]) -> Int {
var duplicate = 0
var seen = Set<Int>()
for num in nums {
if seen.update(with: num) != nil {
duplicate = num
break
}
}
return duplicate
}
}