3. 數組中重復的數字

題目鏈接

牛客網

題目描述

在一個長度為 n 的數組里的所有數字都在 0 到 n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字是重復的，也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。

Input:
{2, 3, 1, 0, 2, 5}Output:
2

解題思路

要求時間復雜度 O(N)，空間復雜度 O(1)。因此不能使用排序的方法，也不能使用額外的標記數組。

對于這種數組元素在 [0, n-1] 范圍內的問題，可以將值為 i 的元素調整到第 i 個位置上進行求解。在調整過程中，如果第 i 位置上已經有一個值為 i 的元素，就可以知道 i 值重復。

以 (2, 3, 1, 0, 2, 5) 為例，遍歷到位置 4 時，該位置上的數為 2，但是第 2 個位置上已經有一個 2 的值了，因此可以知道 2 重復：