题目描述

给定一个数组。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。

题解

时间复杂度：$O(n)$
这道题应该是比较简单的，但是题目所给的代码用的不是很习惯。
那么我们就扫一遍记录每个数出现的次数，最后输出即可。这里应该应用了桶排的思想。

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> a(n, 0);
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] < 0) return -1;
            ++a[nums[i]];
        }
        for (int i = 0; i < n; ++i) {
            if (a[i] > 1) return i;
        }
        return -1;
    }
};