287-寻找重复数

LeetCode 287. Find the Duplicate Number

LeetCode-287

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.

Example 1:

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

method 1

简单的解法是把每个数换到它对应的下标位置处，如果那个位置已经放着正确的数了，那这个数就是重复的，不过这样修改了数组

int findDuplicate(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] != i + 1) {
            if (nums[i] == nums[nums[i] - 1]) return nums[i];
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    return 0;
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

method 2：环形链表入口

转化为环形链表入口问题，即142-环形链表II

因为长度为n的数组只包含1-n的元素

index   0   1   2   3   4
nums[i] 1   3   4   2   2

下标与数值可以连接成一条环形链表0->1->3->2->4->2

下标0对应的数字数1，从0到1的映射是0->nums[0]，而1又作为下标映射到3，所以是nums[0]->nums[nums[0]]

如果初始化slow=0,fast=0，那直接相等就不会进入循环了，所以分别初始化为第二个节点和第三个节点

int findDuplicate(vector<int>& nums) {
    int slow = nums[0];     // 第二个节点
    int fast = nums[nums[0]];   // 第三个节点
    while (slow != fast) {
        slow = nums[slow];      // slow走一步
        fast = nums[nums[fast]];// fast走两步 
    }
    int pre1 = 0;   // 一个指针回到开头位置
    int pre2 = slow;    // 另一个不动
    while (pre1 != pre2) {  // 从头开始一起走
        pre1 = nums[pre1];
        pre2 = nums[pre2];
    }
    return pre1;
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

---

LeetCode 442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 $O(n)$ 且仅使用常量额外空间的算法解决此问题。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]

method

交换到正确的位置，如果那个位置已经有正确元素了，说明这个元素就是重复的，但是先不放进结果数组里，等后面遍历的时候再放，不然会重复

vector<int> findDuplicates(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    vector<int> res;
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            res.push_back(nums[i]);
        }
    }
    return res;
}