[LeetCode 笔记] 287. Find the Duplicate Number

前言

　　这题是一题把阵列当成类似 linked list 的题目，目标是找到阵列中重複的元素，因它只对阵列进行了两次循环，而每次循环都是线性时间的运作，时间複杂度可达 O(n)，这里有 JAVA 和 Python 的写法。

题目

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.

给定一个整数阵列 nums 含有 n + 1 个整数，每个整数都在 [1, n] 範围包含里。
nums 中只有一个重複的数字，回传这个重複的数字。
你必须在不能修改 nums 的情况下解决这个问题，而且只能使用常数的记忆体空间。

题目连结：https://leetcode.com/problems/find-the-duplicate-number/

题目限制

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n

All the integers in nums appear only once except for precisely one integer which appears two or more times.

範例

Input: nums = [1,3,4,2,2]Output: 2

Input: nums = [3,1,3,4,2]Output: 3

思路&笔记

暴力的解法是利用双迴圈，找出相等的元素后就是答案，结果超过时间限制 (不採用)

另一种解法，运用 HashSet 方法的特性，找出不能出现的元素

循环 nums 阵列，把每个元素添加到 HashSet 中如果发现某个元素已经存在于 HashSet 中，那么这个元素就是重複的回传这个元素

第三种解法是使用链表的特性，在链表内的元素不会有重複，有重複的话会形成一个环

把当前的元素，当成下一个元素的 index，变成一个类似 linked list 的链表然后设定一组快慢指针，慢指针走一步，快指针走两步，在链表中有重複的元素，快指针会先走到有重複元素的环内，慢指针也会走到有重複元素的环内，这时如果快慢指针都走到相同的元素，代表这个元素就是我们要找的重複的元素例如走过 2 这个元素，后面又再次遇到 2 的时候，代表 2 是重複的元素，然而会形成一个环，在这个有重複元素的还内一直打转另外设定第三个指针检查，用意是找出环的头，无论用慢指针或快指针去和检查指针比对都行，快慢指针是一样的元素

while 迴圈从 0 开始走，到 3 的时候已经遇到一个 2 了，继续走到 4 的时候又遇到一个 2

JAVA 实现

// 暴力的解法是利用双迴圈，找出相等的元素后就是答案，结果超过时间限制 (不採用)class Solution {    public int findDuplicate(int[] nums) {        for (int i = 0; i < nums.length; i++) {            for(int j = i + 1; j < nums.length; j++) {                if (nums[i] == nums[j]){                    return nums[i];                };            };        };        return -1;    };};// 另一种解法，运用 HashSet 方法的特性，找出不能出现的元素class Solution {    public int findDuplicate(int[] nums) {        HashSet<Integer> set = new HashSet<>(); // 集合        for(int num : nums) {            // 添加进去时会判断有没有 (重複元素不会被添加)            if(!set.add(num)) {                return num; // 回传当下这个元素            }        }        return -1;    }}// 第三种解法是使用链表的特性，在链表内的元素不会有重複，有重複的话会形成一个环class Solution {    public int findDuplicate(int[] nums) {        int slow = 0; // 慢指针        int fast = 0; // 快指针        int check = 0; // 确认指针                    while( true ){            slow = nums[slow]; // 取得 index 位置(走一步)            fast = nums[nums[fast]]; // 取得 index 位置后，从位置再取一次新的位置 (等于走两步)                        // 如果快慢指针一样            if( slow == fast ){                break;            }        }                // 找出循环的头        while( true ){            slow = nums[slow];            check = nums[check]; // 检查指针                        // 如果慢指针和检查指针一样            if( slow == check ){                break;            }        }        return check;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def findDuplicate(self, nums: List[int]) -> int:                slow = 0        fast = 0        check = 0                while True:            slow = nums[slow] # 取得 index 位置(走一步)            fast = nums[nums[fast]] # 取得 index 位置后，从位置再取一次新的位置 (等于走两步)                        # 如果快慢指针一样            if slow == fast:                break        # 找出循环的头        while True:            slow = nums[slow]            check = nums[check]                        # 如果慢指针和检查指针一样            if slow == check:                break                return check

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/09/10/LeetCode-287-Find-the-Duplicate-Number-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论