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

2022-1-19

代码实现部分是我手敲的，如果有错误欢迎评论指出哦

题目

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

解题方法一

 /**
     * 暴力双循环
     * @param arr
     * @return
     */
    private static int findRepeatNumber1(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++){
                if (arr[i] == arr[j]){
                    return arr[i];
                }
            }
        }
        return -1;
    }

解题方法二

 /**
     * 利用HashSet集合结构
     *
     * 时间复杂度：O(n)。
     * 遍历数组一遍。使用哈希集合（HashSet），添加元素的时间复杂度为 O(1)，故总的时间复杂度是 O(n)。
     * 空间复杂度：O(n)。不重复的每个元素都可能存入集合，因此占用 O(n) 额外空间。
     *
     * HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。
     * HashSet 允许有 null 值。
     * HashSet 是无序的，即不会记录插入的顺序。
     * HashSet 不是线程安全的， 如果多个线程尝试同时修改 HashSet，则最终结果是不确定的。 您必须在多线程访问时显式同步对 HashSet 的并发访问。
     * HashSet 实现了 Set 接口。
     *
     * @param arr
     * @return
     */
    private static int findRepeatNumber2(int[] arr){
        HashSet<Integer> set = new HashSet<>();
        int repeat = -1;
        for (int num: arr) {
            // 利用HashSet不允许有重复元素特点 添加失败则重复
//            if (!set.add(num)){
//                repeat = num;
//                break; // 找到一个即可跳出
//            }
            if(set.contains(num)) return num;
            set.add(num);
        }
        return repeat;
    }

解题方法三

/**
     * 原地交换
     * 数组元素的 索引 和 值 是 一对多 的关系。
     * 可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i] = i ）。
     * 因而，就能通过索引映射对应的值，起到与字典等价的作用。
     * 时间复杂度 O(N) ： 遍历数组使用 O(N) ，每轮遍历的判断和交换操作使用 O(1) 。
     * 空间复杂度 O(1) ： 使用常数复杂度的额外空间。
     * @param arr
     * @return
     */
    private static int findRepeatNumber3(int[] arr){
        // 2,4,1,0,6,8,5,7,6,3
        // 0,1,2,3,4,5,6,7,8,9
        int i = 0;
        while(i < arr.length) {
            // 如果当前元素值等于其下标值（假设表示位置正确） 直接跳出本次循环 判断下一个
            if(arr[i] == i) {
                i++;
                continue;
            }
            // 如果当前元素值不等于其下标值
            // 如果以当前元素值为下标的元素等于该元素值 则重复直接返回
            if(arr[arr[i]] == arr[i]) return arr[i];
            // 否则交换位置 使得该元素值放在与其 值 相等下标位置处
            int tmp = arr[i];
            arr[i] = arr[tmp];
            arr[tmp] = tmp;
        }
        return -1;
    }