• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/

---

题目地址：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：

[2, 3, 1, 0, 2, 5, 3]

输出：2 或 3

限制：

2 <= n <= 100000

解题方法

Set

看到数据范围是100000，肯定可以判断时间复杂度是O(n)。

这个题只需要我们找到任何一个重复的元素就行了，所以我们可以考虑对整个数组进行一次遍历，遍历的时候使用set保存已经出现过的元素，利用set的查找的效率是O(1)的特征，可以快速的找到新遍历到的元素是否出现过。如果遍历到的元素已经出现过，那么就返回当前元素。

C++代码如下：

class Solution {

public:

    int findRepeatNumber(vector<int>& nums) {

        unordered_set<int> visited;

        for (int num : nums) {

            if (visited.count(num))

                return num;

            visited.insert(num);

        }

        return -1;

    }

};

快慢指针

LeetCode原题，这个思路特别巧妙，使用快慢指针，判断数组中是否有逻辑上的环存在。题目的返回方式需要注意。另外就是注意快慢指针的初始化方式。

Python代码：

# -*- coding:utf-8 -*-

class Solution:

    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]

    # 函数返回True/False

    def duplicate(self, nums, duplication):

        if len(set(nums)) == len(nums):

            duplication[0] = -1

            return False

        fast = nums[nums[0]]

        slow = nums[0]

        while fast != slow:

            fast = nums[nums[fast]]

            slow = nums[slow]

        fast = 0

        while fast != slow:

            fast = nums[nums[fast]]

            slow = nums[slow]

        duplication[0] = nums[fast]

        return True

日期

2018 年 3 月 26 日 – 学车要早起，困= =
2020 年 3 月 15 日 – 两年后重刷此题