题目描述

找出数组中重复的数字。

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

样例

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

时间复杂度 O(n)

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int  n=nums.size();
        for(int i=0;i<nums.size();i++)
            if(nums[i]<0||nums[i]>=n) return -1;
        //i=0 num[i]=2  第2号位置上是5，第2号位置上不是2，则将2与5交换
        //0  1  2  3  4  5  6  7
        //2, 3, 5, 4, 3, 2, 6, 7
        //5     2                   此时0号位置还不是0，则再进行判断


        //i=0 num[i]=5  第5号位置上是2，第5号位置上不是5，则将5与2交换
        //0  1  2  3  4  5  6  7
        //5, 3, 2, 4, 3, 2, 6, 7
        //2              5        此时0号位置还不是0，则再进行判断



        //i=0 num[i]=2  第2号位置上已经是2，表示有重复的2了  结束
        //0  1  2  3  4  5  6  7
        //2, 3, 2, 4, 3, 5, 6, 7
        //2     2                   
        for(int i=0 ;i<n;i++)
        {

            while( nums[i]!=i )
            {
                if(nums[i]==nums[nums[i]])//找到了一个重复元素
                {
                    return  nums[i];
                }
                else //交换  nums[i]  nums[nums[i]
                    swap(nums[i],nums[nums[i]]);

            }

        }
        return -1;
    }
};