P4103.寻找重复数

1000ms

Tried: 1174

Accepted: 435

Difficulty: 5

所属公司 : Hot100

算法与标签>双指针

在线刷题

给定一个包含 $n + 1$ 个整数的数组 nums，其数字都在 $[1, n]$ 范围内（包括 $1$ 和 $n$ ），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数，返回 这个重复的数。

你的解决方案必须 不修改 数组 nums，且只用常量级 $O(1)$ 的额外空间。

输入

4
1 3 4 2 2

输出

思路

解法1:朴素解法

1.构图：把下标当作节点，把 i -> nums[i] 看成一条边。此时站在任意节点 $i$ ，下一步要去的下标是 $nums[i]$

2.找环的入口：从0号节点出发一直走，一定会遇到一个环，环的入口就是重复数字。

样例 [1,3,4,2,2] 的构图示意如下：

Floyd构图示意

做法：用哈希来记录每个位置是否访问过，当下一步 $nums[i]$ 被访问过，则 $nums[i]$ 就是重复数字。

from typing import List
class Solution:
    # 解法1：哈希判重（朴素做法，空间 O(n)）
    def findDuplicate(self, nums: List[int]) -> int:
        # 哈希
        visited = set()
        # 从0号节点出发
        cur = 0
        while True:
            # 每次往后走
            nxt = nums[cur]
            # 如果下一步要去的点已经被访问过，则代表遇到了"环入口"，即重复数字
            if nxt in visited:
                return nxt
            visited.add(nxt)
            cur = nxt
        # 如果题目数据合法，则不会走到这里
        return -1

if __name__ == "__main__":
    n = int(input().strip())
    nums = list(map(int, input().split()))
    # 题面保证 nums 长度是 n + 1
    print(Solution().findDuplicate(nums))

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    // 解法1：哈希判重（朴素做法，空间 O(n)）
    int findDuplicate(vector<int>& nums) {
        // 哈希
        unordered_set<int> visited;
        // 从0号节点出发
        int cur = 0;
        while (true) {
            // 每次往后走
            int nxt = nums[cur];
            // 如果下一步要去的点已经被访问过，则代表遇到了"环入口"，即重复数字
            if (visited.count(nxt)) {
                return nxt;
            }
            visited.insert(nxt);
            cur = nxt;
        }
        // 如果题目数据合法，则不会走到这里
        return -1;
    }
};

int main() {
    int n;
    cin >> n;

    vector<int> nums(n + 1);
    for (int i = 0; i < n + 1; i++) {
        cin >> nums[i];
    }

    cout << Solution().findDuplicate(nums) << endl;

    return 0;
}

import java.util.*;

class Solution {
    // 解法1：哈希判重（朴素做法，空间 O(n)）
    public int findDuplicate(int[] nums) {
        // 哈希
        Set<Integer> visited = new HashSet<>();
        // 从0号节点出发
        int cur = 0;
        while (true) {
            // 每次往后走
            int nxt = nums[cur];
            // 如果下一步要去的点已经被访问过，则代表遇到了"环入口"，即重复数字
            if (visited.contains(nxt)) {
                return nxt;
            }
            visited.add(nxt);
            cur = nxt;
        }
        // 如果题目数据合法，则不会走到这里
        // return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();

        int[] nums = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            nums[i] = input.nextInt();
        }

        System.out.println(new Solution().findDuplicate(nums));

        input.close();
    }
}

算法解释

1.这个图一定有环

因为每个位置都有下一个可以去的地方。从任意点出发，一定能走出无限长的路径。这个时候一定是存在环的。不然走不出无限长的路径。

2.为什么环入口就是重复数字？

环入口节点假设为 $k$ ，则一定是有两个下标 $i,j$ 同时指向了 $k$ , 也就是存在 $nums[i] = nums[j] = k$ 的情况。此时 $k$ 就是重复元素。

3.为什么一定要从0号节点开始走?

从0号节点出发，一定是一个链+环结构。因为0是整个数组的奇异点，没有其他节点能指向它。所以从它出发，必定是先经过链，再经过环

环入口抽象示意

4.为什么不能从其他节点开始走?

从其他节点出发，并不能保证一定能找到链+环的结构。

例如下图所给的例子，[1,1,2,3] , 此时从任意非 $0$ 下标出发，都只能找到一个单环结构，而不是链+环结构。

而单环结构并不能说明它一定是重复数字!!!

使得其他位置失效的极端情况

解法2:Floyd判圈法

上面那个做法不符合 $O(1)$ 空间的需求，考虑更优做法

问题关键：从0开始找环的入口

1.找相遇点

设两个指针 slow、fast，都从 nums[0] 开始。每次 slow 走一步，走两步。如果存在环，快指针一定会在环内追上慢指针。

2.找环的入口

相遇后，slow 停在环内的某个位置

新建指针 ptr1 指向起点 nums[0]，ptr2 指向相遇点 slow

此后，两指针都每次走一步，最终它们会在环入口相遇。

动画解释

代码实现

def findDuplicate(nums):
    # 第一次相遇：找环内相遇点
    slow = nums[0]
    fast = nums[0]
    while True:
        slow = nums[slow]      # 慢指针走一步
        fast = nums[nums[fast]]  # 快指针走两步
        if slow == fast:
            break

    # 第二次相遇：找环的入口
    ptr1 = nums[0]
    ptr2 = slow
    while ptr1 != ptr2:
        ptr1 = nums[ptr1]
        ptr2 = nums[ptr2]
    return ptr1

# 读取输入并输出结果
if __name__ == "__main__":
    n = int(input().strip())
    nums = list(map(int, input().split()))
    print(findDuplicate(nums))

#include <bits/stdc++.h>
using namespace std;

// 寻找重复数（Floyd 判圈法）
int findDuplicate(const vector<int>& nums) {
    // 第一次相遇：找环内相遇点
    int slow = nums[0];
    int fast = nums[0];
    do {
        slow = nums[slow];          // 慢指针走一步
        fast = nums[nums[fast]];    // 快指针走两步
    } while (slow != fast);

    // 第二次相遇：找环的入口
    int ptr1 = nums[0];
    int ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = nums[ptr1];
        ptr2 = nums[ptr2];
    }
    return ptr1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> nums(n + 1);
    for (int i = 0; i < n + 1; i++) {
        cin >> nums[i];
    }
    cout << findDuplicate(nums) << "\n";
    return 0;
}

import java.util.Scanner;

public class Main {
    // 寻找重复数
    public static int findDuplicate(int[] nums) {
        // 第一次相遇：找环内相遇点
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];          // 慢指针走一步
            fast = nums[nums[fast]];    // 快指针走两步
        } while (slow != fast);

        // 第二次相遇：找环的入口
        int ptr1 = nums[0];
        int ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        return ptr1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(findDuplicate(nums));
        sc.close();
    }
}

面试问答

1. 本题的核心思路是什么？

把数组看成一张有向图，下标 i 指向 nums[i]。因为一共有 n+1 个位置，但值只在 1~n 之间，所以这张图一定有环，而重复数字其实就是环入口，因为环入口代表着同时有两个下标指向这里，也就是存在 $nums[i] = nums[j]$ 。接着用 Floyd 判圈法，先用快慢指针找到环内相遇点，再让一个指针回到起点，两个指针同步往前走，它们再次相遇的位置就是环入口，也就是答案。整个过程时间复杂度 O(n)，额外空间 O(1)。

输入

预期输出（选填）

P4103.寻找重复数

解法1:朴素解法

算法解释

解法2:Floyd判圈法

动画解释

代码实现

面试问答

Status

Development

Support

About