LeetCode287 寻找重复数

发表于 | 分类于 |
字数统计: 269 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/find-the-duplicate-number/

题面

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

解法

有多种解法，包括二分，交换，快慢指针

代码

二分解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size();
        while(l < r) {
            int mid = (l + r) / 2, cnt = 0;
            for (int n: nums) {
                if (n <= mid) {
                    cnt++;
                }
            }
            if (cnt <= mid) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        return l;
    }
};

交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        // vector<int> g(n + 1);
        while(1) {
            for (int i = 0; i < n; i++) {
                if (nums[i] == i + 1) {
                    continue;
                }
                if (nums[i] == nums[nums[i] - 1]) return nums[i];
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        return 0;
    }
};

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
        } while(fast != slow);
        slow = 0;
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};