287. Find the Duplicate Number

題目敘述

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 <= 105
• nums.length == n + 1
• 1 <= 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

/**
 * @param {number[]} nums
 * @return {number}
 */
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
{

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    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
    }
}