题解 | #数组中重复的数字#

JZ50 数组中重复的数字

题意分析：

找出数组中重复的元素。

示例输入：[2,3,1,0,2,5,3]
返回：数组中2和3都出现了多次，返回2或3都可以。

题解一（map统计）：

我们使用map<int,int>进行统计即可。如果m[i]>0,说明元素i是我们要的结果。如果m[i]==0,m[i]++;

int duplicate(vector<int> &numbers) {
    map<int, int> m;
    for (int i = 0; i < numbers.size(); i++) {
        if (m[numbers[i]] > 0) {
            return numbers[i];
        }
        m[numbers[i]]++;
    }
    return -1;

时间复杂度： $O(N)$ ，N为数组长度。

空间复杂度： $O(N)$ 。

题解二（排序）：

我们对数组sort一下，相同的元素肯定相邻，因此我们可以这样写。

int duplicate(vector<int> &numbers) {
    if (numbers.empty()) return -1;
    sort(numbers.begin(), numbers.end());
    for (int i = 0; i < numbers.size() - 1; i++) {
        if (numbers[i] == numbers[i + 1]) {
            return numbers[i];
        }
    }
    return -1;
}

时间复杂度： $O(nlog \ n)$ 。排序需要 $O(nlog \ n)$

空间复杂度：暂定，依托于使用的排序算法。

题解三（将数组的下标作为哈希key）

题目说了，数组中的所有数字大小范围在0到n-1之间。数组的长度为n。这个条件能不能使用呢？

我们将nums[i]放在索引值i下面。如果后面有发现nums[i]索引的位置的元素等于nums[i]，即nums[nums[i]]==nums[i]。说明有nums[i]处的坑被占据了，发生了重复。新来的数nums[i]即为重复元素。

通过不断的将nums[i]交换到索引nums[i]处，即可找到结果。
图片说明

int duplicate(vector<int> &numbers) {
    int i = 0;
    while (i < numbers.size()) {
        if (numbers[i] == i) {
            i++;
            continue;
        }
        if (numbers[numbers[i]] == numbers[i])
            return numbers[i];
        swap(numbers[i], numbers[numbers[i]]);
    }
    return -1;
}

时间复杂度： $O(N)$ ，N为数组长度，我们可能最坏需要遍历一遍数组。

空间复杂度： $O(1)$ 。没有申请试用额外空间内存。