数组中重复的数字

题目描述

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

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

解题思路

1.遍历法

先定义一个集合set，从头开始遍历数组中的元素，每遍历一个元素就将该元素插入到定义的集合中，由于集合中的元素不能有重复，因此当插入集合失败时，这个插入失败的元素就是我们要找的重复数字。C++代码实现如下：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        // 定义一个集合s
        set<int> s;
        // 保存insert函数的返回值，集合插入失败时p.second 为bool值false
        pair<set<int>::iterator, bool> p;
        // 遍历数组中的元素
        for(int i=0; i<nums.size(); i++){
            p = s.insert(nums[i]);
            if(!p.second)
                return nums[i];
        }
        // 没有重复元素时返回 -1 
        return -1;
    }
};

2.下标定位法

n个数字都在0～n-1范围内，如果没有重复的数字，并且数组是有序的，排好序后数字m应该刚好在下标m的位置上。从头到尾扫描数组，当扫描到下标为i的数字时，首先比较这个数字m是否等于下标i，如果等于就继续扫描下一个数字，如果不等于，就让它和第m个数字进行比较，如果它和第m个数字相等，那么出现了重复直接返回这个数字，如果不相等，则将它和第m个数字进行交换，即把m放到第m个位置上。重复这个过程，直到出现一个重复的数字。C++代码实现如下：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            //下标为i的位置上的元素nums[i]不是i时和下标为nums[i]位置的元素做比较
            while(nums[i] != i){  
                // 下标为nums[i]位置的元素也为nums[i]时，出现重复数字
                if(nums[nums[i]] == nums[i])
                    return nums[i];
                else{  // 下标为nums[i]位置的元素不为nums[i]时，将它和下标为i位置的元素做交换
                    int temp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = temp;
                }
            }
        } //没有重复数字时，返回-1 
        return -1;
    }
};