LeetCode 287 Find the Duplicate Number

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-03-07 15:04:45
    编辑于：2022-03-07 15:19:46
    浏览量：1023

概述

https://leetcode.com/problems/find-the-duplicate-number/

这是剑指 Offer 上的原题来着。

仅有一个重复数字，要求不能修改 nums，且常量空间复杂度。

使用符号进行标记

不能修改原数组，也只能常量空间复杂度，使得我们不能排序。

我偏要修改原数组，之后再给他改回去不就行了。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int target = -1;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[abs(nums[i])] < 0) {
                target = abs(nums[i]);
            } else {
                nums[abs(nums[i])] *= -1;
            }
        }
        for (auto& n : nums) n = abs(n);
        return target;
    }
};

链表法

https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.

把数组视为链表，找重复点的问题转换成了找带有环的链表的环的开始点。

数组中显然可能有多个环怎么办？没关系，只要我们是从 nums[0] 开始的，就必然处在那个正确的带环的链表中，因为没有节点能跳到 0 处。

There could be multiple cycles in our 'graph'. But the beauty of this problem is that nums[0] is always the entrance to the cycle which has duplicate numbers, because no one can jump back to nums[0].

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

Links: leetcode-287-find-the-duplicate-number