例题-数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

原理

对于题目所给的条件，可以开辟一个与给定数组等长的新数组，用于记录给定数组中出现的数字的个数（新数组的下标即表示给定数组中的数，数组存放的值，即为该数字出现的次数）一旦新数组中某个记录的数大于1，则返回新数组的下标

代码实现

class Solution {
public:
    int duplicate(vector<int>& numbers) {
        int lenth = numbers.size();
        int vec[lenth];
        memset(vec, 0, sizeof(vec));
        for(int i :numbers){
            if(!vec[i])
                vec[i]++;
            else
                return i;
        }
        return -1;
    }
};

例子

输入

[2,3,1,0,2,5,3]

输出

2或3