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

题目的主要信息：

• 一个长度为$nn$的数组中只有0到$n-1n-1$的数字
• 需要找出其中任意一个重复出现的数字

举一反三：

学习完本题的思路你可以解决如下题目：

JZ56. 数组中只出现一次的两个数字

JZ50. 第一个只出现一次的字符

JZ75. 字符流中第一个不重复的字符

方法一：位置重排（推荐使用）

思路：

既然数组长度为$nn$只包含了0到$n-1n-1$的数字，那么如果数字没有重复，这些数字排序后将会与其下标一一对应。那我们就可以考虑遍历数组，每次检查数字与下标是不是一致的，一致的说明它在属于它的位置上，不一致我们就将其交换到该数字作为下标的位置上，如果交换过程中，那个位置已经出现了等于它下标的数字，那肯定就重复了。

具体做法：

• step 1：遍历数组，遇到数组元素与下标相同的不用管。
• step 2：遇到数组元素与下标不同，就将其交换到属于它的位置，交换前检查那个位置是否有相同的元素，若有则重复。
• step 3：遍历结束完全交换也没重复，则返回-1.

图示：

Java实现代码：

import java.util.*;
public class Solution {
    //交换函数
    private void swap(int[] numbers, int a, int b){
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
    }
    public int duplicate (int[] numbers) {
        for(int i = 0; i < numbers.length; i++){
            //该位置本来就是对的
            if(numbers[i] == i)
                continue;
            //位置不对，需要换到自己对应的位置
            else{
                //对应位置相等，重复
                if(numbers[i] == numbers[numbers[i]])
                    return numbers[i];
                //交换位置
                else{
                    swap(numbers, i, numbers[i]);
                  	i--;
                }
            }
        }
        //没有重复
        return -1;
    }
}

C++实现代码：

class Solution {
public:
    int duplicate(vector<int>& numbers) {
        for(int i = 0; i < numbers.size(); i++){
            //该位置本来就是对的
            if(numbers[i] == i)
                continue;
            //位置不对，需要换到自己对应的位置
            else{
                //对应位置相等，重复
                if(numbers[i] == numbers[numbers[i]])
                    return numbers[i];
                //交换位置
                else{
                    swap(numbers[i], numbers[numbers[i]]);
                  	i--;
                }
            }
        }
        //没有重复
        return -1;
    }
};

Python实现代码：

class Solution:
    #交换函数
    def swap(self, numbers: List[int], a: int, b: int):
        temp = numbers[a]
        numbers[a] = numbers[b]
        numbers[b] = temp
    
    def duplicate(self , numbers: List[int]) -> int:
        for i in range(len(numbers)):
            #该位置本来就是对的
            if numbers[i] == i:
                continue
            #位置不对，需要换到自己对应的位置
            else:
                #对应位置相等，重复
                if numbers[i] == numbers[numbers[i]]:
                    return numbers[i]
                #交换位置
                else:
                    self.swap(numbers, i, numbers[i])
                    i -= 1
        #没有重复
        return -1

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组长度，遍历一次数组，所有的交换都是$O(1)O(1)$
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间

方法二：哈希表（扩展思路）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

既然是找重复的问题，那我们利用哈希表记录频率也是一样可以的。只要遇到的元素在哈希表中出现过，它就重复了。

具体做法：

• step 1：遍历数组，将没有出现过的元素加入哈希表。
• step 2：遇到的元素在哈希表中出现过就是重复数组。
• step 3：遍历结束也没找到就返回-1.

Java实现代码：

import java.util.*;
public class Solution {
    public int duplicate (int[] numbers) {
        //哈希表记录重复
        HashMap<Integer, Integer> mp = new HashMap<>();
        //遍历数组
        for(int i = 0; i < numbers.length; i++){
            //如果没有出现过就加入哈希表
            if(!mp.containsKey(numbers[i]))
                mp.put(numbers[i], 1);
            //否则就是重复数字
            else
                return numbers[i];
        }
        //没有重复
        return -1;
    }
}

C++实现代码：

class Solution {
public:
    int duplicate(vector<int>& numbers) {
        //哈希表记录重复
        unordered_map<int, int> mp;
        //遍历数组
        for(int i = 0; i < numbers.size(); i++){
            //如果没有出现过就加入哈希表
            if(mp.find(numbers[i]) == mp.end())
                mp[numbers[i]]++;
            //否则就是重复数字
            else
                return numbers[i];
        }
        //没有重复
        return -1;
    }
};

Python实现代码：

class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        #哈希表记录重复
        mp = dict()
        #遍历数组
        for num in numbers:
            #如果没有出现过就加入哈希表
            if num not in mp:
                mp[num] = 1
            #否则就是重复数字
            else:
                return num
        #没有重复
        return -1

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组长度，遍历一次数组，哈希表每次操作都是$O(1)O(1)$
• 空间复杂度：$O(n)O(n)$，哈希表最大的空间为数组长度