剑指 Offer 03. 数组中重复的数字

题目地址：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

题目的主要信息：

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

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

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

一、HashSet

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

具体做法：

• step1：创建一个HashSet集合。
• step2：遍历数组。
• step3：如果HashSet集合中不存在当前元素，则添加进HashSet集合中。
• step4：如果HashSet集合中存在当前元素，说明前面已经向HashSet中添加过了该元素，所以该元素在数组中重复了。
• step5：存在不合法输入（即数组不合法），则输出-1。

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

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

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

复杂度分析：

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

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

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

解题思路：

• step1：对数组进行排序（升序 或 降序均可），有序数组中，重复的元素肯定是相邻的。
• step2：判断相邻元素是否相等，如果相等，则该元素重复了。
• step3：存在不合法输入（即数组不合法），则输出-1。

import java.util.Arrays;

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

    public int findRepeatNumber(int[] nums) {
        // 1、对数组元素进行升序排序
        Arrays.sort(nums);
        // 2、遍历数组
        for (int i = 0; i < nums.length - 1; i++) {
            // 3、如果相邻两个元素相等，则该元素重复了，直接return返回
            if (nums[i] == nums[i + 1]) {
                return nums[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范围内。所以可以使用下面的解题思路。

具体做法：

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

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().findRepeatNumber(new int[]{1, 2, 2}));
    }

    public int findRepeatNumber(int[] nums) {
        // 优先处理特殊情况
        if (nums.length <= 1) return -1;

        int i = 0;
        while (i < nums.length) {
            //如果元素和下标相等，则比较下一个元素
            if (nums[i] == i) {
                i++;
            } else {
                //对应位置相等，证明该元素重复了
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }

                //如果不相等，则交换元素位置
                int temp = nums[nums[i]];
                nums[numbers[i]] = nums[i];
                nums[i] = temp;

				//注意：这里交换元素，不能这样写，否则可能会死循环。（传入[1，2，2]调试一下就知道原因了）
				//int temp = nums[i];
				//nums[i] = nums[nums[i]];
				//nums[nums[i]] = temp;
            }
        }

        // 3、如果不存在重复数字，则返回 -1
        return -1;
    }
    
}

注意：官方题解中的做法是错误的，因为在做交换的时候，交换后的是有可能就是重复数字，但是i++，校验就被忽略了，将 [1，2，2] 传入验证可知。如果要使用for循环来遍历，可以使用如下写法：

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().findRepeatNumber(new int[]{1, 2, 2}));
    }

    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (i != nums[i]) {
                //对应位置相等，证明该元素重复了
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }

                //如果不相等，则交换元素位置
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }
        //没有重复
        return -1;
    }

}

复杂度分析：

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

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

总结：

• 第三种做法的最好。（看到 长度为n的数组中只有0到n−1的数字 这类题时，可以考虑使用这种方式）

• 普遍认为 第一种做法 比 第二种做法好。因为我们更多关注的是时间复杂度，对于空间复杂度反而不那么关注。（很多时候往往会牺牲空间换时间）