Leetcode.287.Find the Duplicate

题目

给定n+1个数字，数字都是从1~n的数字，这些数字只有1个重复数字，找出重复数字。
要求：空间复杂度为O(1)，不能移动数组。

Input： 2,2,2
Output：2
Input：1,3,4,2,2
Output：2
Input： 3,1,3,4,2
Output：3

思路1

直接循环暴力求解。

int findDuplicate(vector<int>& nums) {

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

思路2

类似于二分法。由于数字从1_{n，所以当1}n/2的数字小于n/2时，数字一定在上半区。

int findDuplicate(vector<int>& nums) {
    int low = 1, high = (int)nums.size()-1;
    while (low < high) {
        int mid = (low + high) / 2;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= mid) count++;
        }
        if (count > mid) {
            high = mid;
        } else {
            low = mid+1;
        }
    }
    return high;
}

总结

灵活运用条件，找到不变量和变量。