LeetCode 287 Find the Duplicate Number

Tag: 数组类题目 LeetCode Posted on 2022-03-07 15:04:45 Edited on 2022-03-07 15:19:46 Views: 134

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/