03.数组中重复的数字 (Easy)*

题目描述*

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0 ～ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例*

输入：[2, 3, 1, 0, 2, 5, 3]

输出：2 或 3

限制*

2 <= n <= 100000

代码*

如果不要求空间复杂度，用标记数组就能解决。

要求时间复杂度 O(N)，空间复杂度 O(1)，既然长度为 n 的数组内的值范围在 0 ~ n - 1 内，那么我们可以利用数组下标判断是否重复。

把值为 i 的项交换到下标 i 上，如果交换过程中遇到值等于对应位置的值，那么返回值。

剑指 offer 上提供了一种不允许修改数组的解法，运用二分查找的思想：n + 1 长的数组的值都在 1 ~ n 范围内，取中间值 m，把范围划分为 1 ~ m 和 m + 1 ~ n，如果 1 ~ m 区间的数字数目超过 m，那这一半区间一定有重复的数字。以此思想每次将区间一分为二。但这种方法显然并不能适用于所有情况，如 [0, 1, 2, 0, 4, 5, 6, 7, 8, 9]，首先我们要检测 0 ~ 4 的值数量，结果为 5，未检测出重复，然后去检测 5 ~ 9，当然也不会检测到重复，导致结果返回 -1。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        if(nums.size() <= 0) {
            return -1;
        }
        for(int i = 0; i < nums.size(); i++) {
            // 交换直至值与下标相等
            while(nums[i] != i) {
                if(nums[nums[i]] == nums[i]) {
                    return nums[i];
                }else {
                    swap(nums[nums[i]], nums[i]);
                }
            }
        }
        return -1;
    }
};