LeetCode：287. Find the Duplicate Number（找出重复的数）

超、凢脫俗 2022-04-04 06:28 123阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：（利用set集合的形式）

python实现方式1:

java实现方式2:（快慢指针）

python实现方式2：

源码github地址：

--------------------

### 题目描述： ###

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
    输出: 2

示例 2:

输入: [3,1,3,4,2]
    输出: 3

说明：

不能更改原数组（假设数组是只读的）。  
只能使用额外的 O(1) 的空间。  
时间复杂度小于 O(n2) 。  
数组中只有一个重复的数字，但它可能不止重复出现一次。

--------------------

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

--------------------

### java实现方法1：（利用set集合的形式） ###

/**
         * 重复数字
         *
         * @param nums 数组
         * @return int
         */
        private int findDuplicateNumber2(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                if (!set.contains(num)) {
                    set.add(num);
                } else {
                    return num;
                }
            }
            return -1;
        }

时间复杂度：O(n）

空间复杂度：O(1)

--------------------

### python实现方式1: ###

def find_duplicate_number2(nums: List[int]) -> int:
        '''
           找出重复的数字
       Args:
           arr: 数组
       Returns:
           重复数字
       '''
        s = set()
        for num in nums:
            if num in s:
                return num
            else:
                s.add(num)
        return -1

时间复杂度：O (n）

空间复杂度：O (1)

--------------------

### java实现方式2:（快慢指针） ###

快慢指针，证明在第二次相遇就是环中交点：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5MzQ1MjkzNzIx_size_16_color_FFFFFF_t_70][]

/**
         * 快慢指针方式找出重复的数
         *
         * @param nums 数组
         * @return num
         */
        public int findDuplicateNumber3(int[] nums) {
            if (nums.length < 1) {
                return -1;
            }
            // 找出里面的环
            int slow = nums[0];
            int fast = nums[nums[0]];
            while (slow != fast) {
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            // 另外一只兔子从原点出发，一定会在重复点出和另外一个乌龟相遇
            int slow2 = 0;
            while (slow2 != slow) {
                slow2 = nums[slow2];
                slow = nums[slow];
            }
            return slow2;
        }

时间复杂度：O (n）

空间复杂度：O (1)

--------------------

###  python实现方式2： ###

def find_duplicate_number3(self, nums: List[int]) -> int:
            '''
                快慢指针思想, fast 和 slow 是指针
           Args:
               arr: 数组
           Returns:
               重复数字
           '''
            # 找到环的位置
            slow = nums[0]
            fast = nums[nums[0]]
            while slow != fast:
                slow = nums[slow]
                fast = nums[nums[fast]]
            # 另外一只乌龟从原点出发，在重复点时候相遇
            slow2 = 0
            while slow2 != slow:
                slow = nums[slow]
                slow2 = nums[slow2]
            return slow2

时间复杂度：O (n）

空间复杂度：O (1)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5MzQ1MjkzNzIx_size_16_color_FFFFFF_t_70]: /images/20220404/7a75ec26104e46e380c446473e46e5b3.png
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode