3.数组中重复的数字.md

3.数组中重复的数字

题目描述

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

示例1

输入

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

返回值

2

思路 & 解答

我们首先可能想到的做法，就是借助 set，如果元素不存在 set中，就将元素添加进去，如果 set 中包含该元素，就返回该元素即可。如果一直都没有重复的，那么最后返回 -1。

Java 代码如下：

import java.util.*;
public class Solution {
    public int duplicate(int[] numbers) {
        if (numbers != null) {
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < numbers.length; i++) {
                if (set.contains(numbers[i])) {
                    return numbers[i];
                } else {
                    set.add(numbers[i]);
                }
            }
        }
        return -1;
    }
}

C++ 代码如下：

#include <iostream>
#include <vector>
#include<set>

using namespace std;

class Solution {
public:
    int duplicate(vector<int> &numbers) {
        if (!numbers.empty()) {
            set<int> mySet;
            for (int i = 0; i < numbers.size(); i++) {
                if (mySet.count(numbers[i]) <= 0) {
                    return numbers[i];
                } else {
                    mySet.insert(numbers[i]);
                }
            }
        }
        return -1;
    }
};

以上代码的时间复杂度为O(n)，因为最差的情况可能遍历完所有的元素；空间复杂度也是 O(n)，最大需 要set 大小为 n。

当然除了set，我们也可以直接借助数组，因为所有数字都在 0 到 n-1 的范围内，我们用一个大小为 n 的数组，就可以对所有的数字进行统计个数，如果个数超过 1，那么肯定是重复的数字，如果没有重复的数字，则返回 -1；

Java 代码实现：

public class Solution {
    public int duplicate(int[] numbers) {
        if (numbers != null) {
            int[] nums = new int[numbers.length];
            for (int i = 0; i < numbers.length; i++) {
                if (nums[numbers[i]] == 1) {
                    return numbers[i];
                } else {
                    nums[numbers[i]] = 1;
                }
            }
        }
        return -1;
    }
}

C++ 代码实现：

#include <iostream>
#include <vector>
#include<set>

using namespace std;

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

同样这种做法的时间复杂度和空间复杂度都是 O(n),并没有优化太多。

那么有没有空间复杂度为O(1)的做法呢？

肯定是有的，不借助额外的空间，那么就只能操作原数组了。如果没有重复的情况，那么这些数字排序后，数字i和数组下标i应该是一一对应的。不会出现多个数字i的情况。

基于这个原则，我们在遍历数组的时候，将元素 i 调整到下标 i 的位置，如果下标i的位置已经有元素，那么说明冲突了，这个元素肯定是重复的，否则继续调整后面的。如果没有发现重复的数字，就返回 -1。

Java代码实现如下：

public class Solution {
    public int duplicate(int[] numbers) {
       int i = 0;
        while(i < numbers.length) {
            if(numbers[i] == i) {
                i++;
                continue;
            }
            if(numbers[numbers[i]] == numbers[i]) return numbers[i];
            int tmp = numbers[i];
            numbers[i] = numbers[tmp];
            numbers[tmp] = tmp;
        }
        return -1;
    }
}

C++ 代码实现如下：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    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];
            }
            int tmp = numbers[i];
            numbers[i] = numbers[tmp];
            numbers[tmp] = tmp;
        }
        return -1;
    }
};

但是上面的做法，不适合求解多个重复数字的例子，因为调换的时候，很容易将后面的数字换到前面去，就会导致求解出来不是第一个重复的数字（可以用来求解任意的重复数字），可能是第2，3...或者其他的重复数字。譬如：[6,3,2,0,2,5,0]正确的解应该是 2 ，但是由于第一次把 6 和最后的0 调换了位置，就会导致求解出来的值为 0 。