寻找重复数

题意

在 n+1 个元素（值域 [1,n]）中找重复数，不修改数组，O(1) 空间。

思路

把 nums[i] 视为从 i 到 nums[i] 的 next 指针，数组构成一个有环链表（重复值导致两个节点指向同一后继）。Floyd 快慢指针找环入口即为重复数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        int slow = nums[0], fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().findDuplicate(a) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#!/usr/bin/env python3
from typing import List


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().findDuplicate(a))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。

总结

把数组值视为 next 指针是本题的关键映射。重复数意味着两个位置指向同一个后继，形成环。Floyd 找环入口的证明与链表环检测完全相同。

目录

题意

思路

代码

复杂度

总结