根据acwing题库搜索剑指, 一直往下刷。

1. 找出数组中重复的数字

// 我看到数据范围，先写的暴力，可以过。
// 听了y总的写法确实女少啊。
// 暴力：
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++)
        {
            for (int j = 0; j < nums.size(); j ++)
            {
                if (i == j) continue;
                if (nums[i] == nums[j]) return nums[i];
            }
        }
    }
};

// O(nlogn)时间
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            int cnt = 0;
            for (auto x : nums) cnt += (x >= l && x <= mid);
            if (cnt > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};