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

数组中重复的数字

https://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524

题目地址：https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=265

题目的主要信息：

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

注意：题目只要求找出任意一个重复出现的数字即可，而不是找出所有重复出现的数字。我开始时就是没读清楚题目，找出了全部重复出现的数字，所以没通过。

针对这道题，给出三种解题方式：① 元素位置重排序、② 有序数组相邻元素比较、③ HashSet不重复元素。

一、HashSet

看到这道题，相信很多人第一反应就是使用HashSet来解答：

解题思路：

1、创建一个HashSet集合。

2、遍历数组。

3、如果HashSet集合中不存在当前元素，则添加进HashSet集合中。

4、如果HashSet集合中存在当前元素，说明前面已经向HashSet中添加过了该元素，所以该元素在数组中重复了。

5、存在不合法输入（即数组不合法），则输出-1。

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 2, 3, 0, 5, 3};
        System.out.println(new Solution().duplicate(numbers));
    }

    public int duplicate(int[] numbers) {
        // 1、创建Set集合
        Set<Integer> set = new HashSet<>();
        // 2、遍历数组
        for (int i : numbers) {
            // 3、如果Set集合中存在该元素，则证明前面已经向Set集合中添加过元素了，所以该元素是重复的。
            if (set.contains(i)) {
                return i;
            } else {
                // 4、如果Set集合中没有该元素，则添加进Set集合中
                set.add(i);
            }
        }
        // 5、如果数组中不存在重复元素，则返回 -1
        return -1;
    }
}

复杂度分析：

代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。使用了额外辅助空间 → Set集合，空间复杂度为O(n)

时间复杂度：O(n)
空间复杂度：O(n)

二、有序数组相邻元素比较

解题思路：

1、对数组进行排序（升序或降序均可），有序数组中，重复的元素肯定是相邻的。

2、判断相邻元素是否相等，如果相等，则该元素重复了。

3、存在不合法输入（即数组不合法），则输出-1。

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 2, 3, 0, 5, 3};
        System.out.println(new Solution().duplicate(numbers));
    }

    public int duplicate(int[] numbers) {
        // 1、对数组元素进行升序排序
        Arrays.sort(numbers);
        // 2、遍历数组
        for (int i = 0; i < numbers.length - 1; i++) {
            // 3、如果相邻两个元素相等，则该元素重复了，直接return返回
            if (numbers[i] == numbers[i + 1]) {
                return numbers[i];
            }
        }
        // 4、如果不存在重复数字，则返回 -1
        return -1;
    }
}

复杂度分析：

Arrays.sort() 根据入参类型选择以下排序算法：

基本类型数组使用快速排序。（快速排序的时间复杂度为O(nlogn) ，空间复杂度为O(logn) )
对象数组使用归并排序。（归并排序的时间复杂度为O(nlogn)，空间复杂度为O(1) ）

由于rucan为 int[] 基本类型数组，所以是快速排序

时间复杂度：O(nlogn)
空间复杂度：O(logn)

三、数组元素对比与位置交换（推荐）

因为题目中有一段描述：长度为n的数组，它里面的元素都在0到n-1范围内。所以可以使用下面的解题思路。

解题思路：

1、遍历数组，遇到数组元素与下标相同的不用管。

2、遇到数组元素与下标不同，就将其交换到属于它的位置，交换前检查那个位置是否有相同的元素，若有则重复。

3、遍历结束完全交换也没重复，则返回 -1

public class Solution {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 2, 3, 0, 5, 3};
        System.out.println(new Solution().duplicate(numbers));
    }

    public int duplicate(int[] numbers) {
        int i = 0;
        while (i < numbers.length) {
            // 1、如果数组元素与下标相同，比较下一个下标和它对应的元素
            if (numbers[i] == i) {
                i++;
            } else {
                // 2、遇到数组元素与下标不同，就将其交换到属于它的位置，但在交换前先检查那个位置是否有相同的元素，若有则重复。
                if (numbers[i] == numbers[numbers[i]]) {
                    return numbers[i];
                } else {
                    // 交换元素位置
                    int temp = numbers[i];
                    numbers[i] = numbers[numbers[i]];
                    numbers[numbers[i]] = temp;
                }
            }
        }
        // 3、如果不存在重复数字，则返回 -1
        return -1;
    }
}

复杂度分析：

代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。使用了常数级变量，无额外辅助空间，空间复杂度为O(1)