【leetcode】287. 寻找重复数

题目内容

287. 寻找重复数

思路分析

本题由于二分查找的条件劝退，一连拖了好几天，拖的有点恶心了，就只好留了些坑把这个题先跳过了。

本题主要是要求使用O(n)的时间复杂度和O(1)的空间复杂度，这个要求卡死了很多解法。

除了这里用的二分法以外，常见的另一种方法还有快慢指针法，见方法二-参考资料一。

方法一：基数排序（其实不符合题目要求，但能过）

由于在164. 最大间距中刚刚用过了基数排序这种时间复杂度为O(n)的办法，就想着用基数排序做一下，没想到还过了。思路很简单，就是先排序然后再遍历排序后的数组找重复的数。

但是这种解法并不符合题目要求。

方法二：二分法

参考资料一

参考资料二

写二分法是真的被写吐了，第一次见识到二分法这么难写（例如left和right的范围、while的终止条件、left和right的赋值、最终是返回left/mid/right等等）。关于二分法labuladong在知乎的这个回答看了下写的挺好的，留个坑以后再看吧...现在不想看了。

思路就是设数组中小于等于某个数num的数字个数为cnt，则会有以下性质：

若重复的数字为dup，则大于等于dup的数字num都满足cnt大于num，小于dup的数字num都满足cnt小于等于num。（即参考资料二中的抽屉定理）

根据这个性质，再结合长为n的数组中的数的范围为[1, n-1]，即可以对这些数字进行二分查找。不断地二分，以查找cnt大于num的左边界。

代码

#include <vector>
#include <iostream>
#include <math.h>
#include <limits.h>
#include <unordered_set>
#include <algorithm>

using namespace std;

// 基数排序
// 时间复杂度O(n)
// 空间复杂度O(n)
// 其实不符合题意，但能通过
class Solution1 {
public:
    int findDuplicate(vector<int>& nums) {
        int max_value = *max_element(nums.begin(), nums.end());
        int digit { 0 }; // nums中最大的位数

        while (max_value != 0) {
            max_value = max_value / 10;
            ++digit;
        }

        for (int i = 0; i < digit; ++i) {
            vector<vector<int>> buckets(10);
            for (auto num : nums) {
                buckets[int(num/pow(10, i))%10].push_back(num);
            }
            nums.clear();
            for (auto bucket : buckets) {
                nums.insert(nums.end(), bucket.begin(), bucket.end());
            }
        }

        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] - nums[i - 1] == 0) {
                return nums[i];
            }
        }

        return -1;
    }
};

// 二分法
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int left{ 1 }, right{ n - 1 }, mid{ 0 }; // 指针代表的是数字而非下标

        while (left <= right) {
            mid = (right + left) / 2;
            int cnt{ 0 }; // nums中的小于等于nums[mid]的数字的个数
            for (auto num : nums) {
                if (num <= mid) cnt++;
            }
            if (cnt <= mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 感觉二分查找的边界条件还是挺难的
        return left;
    }
};

int main() {
    Solution s;
    vector<int> input{ 1,3,4,2,2 };
    // s.quickSort(input, 0, input.size() - 1);
    cout << s.findDuplicate(input) << endl;
}

收获

见识了二分法的魔鬼之处