[LeetCode][287. 寻找重复数] 9种方法(可能是最全的)，拓展思路!

By Long Luo

这篇文章是 287. 寻找重复数 的题解。

目前这道题，经过自己摸索和参考 官方题解: 寻找重复数 ，目前发现了9种方法。

这些方法可以分为以下几类：

• 需要额外空间，需要修改原始数组 $O(logn)$ space
  • 排序 - $O(nlogn)$ time
• 需要额外空间，不修改原始数组 $O(n)$ space
  • 计数法 - $O(n)$ time
  • Set - $O(n)$ time
• 不需要额外空间，需要修改原始数组 $O(1)$ space
  • 标记法 - $O(n)$ time
  • 索引排序 - $O(n)$ time
• 不需要额外空间，不修改原始数组 $O(1)$ space
  • 暴力 - $O(n^2)$ time
  • 二分搜索 - $O(nlogn)$ time
  • 位运算 - O(nlogn) time
  • 双指针 - $O(n)$ time

因为题目要求：

1. 必须不修改数组 $\textit{nums}$；
2. 只用常量级 $O(1)$ 的额外空间。

因此我们先从需要修改数组的方案开始，下面我们就来一一分析：

需要额外空间，需要修改原始数组

方法一：排序

先对数组进行排序，然后遍历数组，如果出现重复数字既是答案。

// Sort
public static int findDuplicate_sort(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    for (int i = 1; i < len; i++) {
        if (nums[i] == nums[i - 1]) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

• 时间复杂度：$O(nlogn + n)$，其中 $n$ 为 $\textit{nums}$ 数组的长度，$O(logn)$ 排序复杂度，总时间复杂度为 $O(nlogn + n)$。
• 空间复杂度：$O(logn)$，排序需要使用 $O(logn)$ 空间。

需要额外空间，不修改原始数组

方法二：计数法

因为数组元素值的范围是 $[1, n]$ 之间，那么可以使用一个数组来记录数字出现次数，次数大于 $1$ 即为答案。

// Count
public static int findDuplicate_count(int[] nums) {
    int len = nums.length;
    int[] cnt = new int[len + 1];
    for (int i = 0; i < len; i++) {
        cnt[nums[i]]++;
        if (cnt[nums[i]] > 1) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\textit{nums}$ 数组的长度。
• 空间复杂度：$O(n)$，需要新建一个长度为 $n$ 的数组。

方法三：HashSet

同方法二，这里使用HashSet来记录数组元素。

// Set
public static int findDuplicate_set(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (!set.add(nums[i])) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\textit{nums}$ 数组的长度。
• 空间复杂度：$O(n)$。

不需要额外空间，需要修改原始数组

方法四：标记法

标记法的思想和计数法是一致的，但这个方法比计数法，$\texttt{Set}$ 更为巧妙。
考虑到数组元素值的范围是 $[1, n]$，但数组长度为 $n + 1$，那么很显然在遍历数组的时候，我们将数组的值变为其对应的负数，那么再次遇到负数就得到了答案。

// Visited
public static int findDuplicate_mark(int[] nums) {
    int len = nums.length;
    for (int num : nums) {
        int idx = Math.abs(num);
        if (nums[idx] < 0) {
            return idx;
        }
        nums[idx] = -nums[idx];
    }

    return len;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\textit{nums}$ 数组的长度。
• 空间复杂度：$O(1)$。

方法五：索引排序

索引排序是更难想到的方法。

数组排序之后，每个数组元素的值是其索引值 $index + 1$，那么就可以进行如此操作：

1. 如果 $\textit{nums}[i] == i + 1$，说明已经排好序了，那么跳过，$i++$；
2. 如果 $\textit{nums}[i] == \textit{nums}[\textit{nums}[i] - 1]$，说明在正确的索引已经有一个值了，那么这个值就是重复的元素；
3. 上述均不满足，交换 $\textit{nums}[i]$ 和 $\textit{nums}[\textit{nums}[i] - 1]$ 的值。

// Index Sort
// n+1 numbers in n.
public static int findDuplicate_index_sort(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len; ) {
        int n = nums[i];
        if (n == i + 1) {
            i++;
        } else if (n == nums[n - 1]) {
            return n;
        } else {
            nums[i] = nums[n - 1];
            nums[n - 1] = n;
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\textit{nums}$ 数组的长度。
• 空间复杂度：$O(1)$。

不需要额外空间，不修改原始数组

方法六：暴力2重循环

如果不允许额外空间，不允许修改原始数组，大多数人反而不会想到这个方法。

这个方法会超时。

// 2 Loops
public static int findDuplicate_2loops(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }

    return len;
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 为 $\textit{nums}$ 数组的长度。
• 空间复杂度：$O(1)$。

方法七：二分搜索

这里感谢大神 @liweiwei1419 的 详细题解 ，大家可以参考他的详细题解进行理解。

二分搜索是用来在有序数组里查找某个特定的值，但是这个数组并不是有序的，咋一看不适合使用二分搜索算法。

因为题目中规定了数组里元素大小在 $[1, n]$ 之间，而在 $[1, n]$ 之间找一个整数，并不是在输入数组中查找某个整数，所以这道题可以使用二分查找。

二分查找的思路是先猜一个数（在有效范围 $[\textit{left}, \textit{right}]$ 里位于中间的数 $\textit{mid}$），那么这个中间数和哪个数进行比较呢？

如果目标数 $\textit{target}$ 小于 $\textit{mid}$，那么统计原始数组，小于等于 $\textit{mid}$ 的元素的个数 $\textit{cnt}$，$cnt \gt mid$，反之 $cnt \leq mid$ 。

// Binary Search
public static int findDuplicate_bs(int[] nums) {
    int len = nums.length;
    int low = 1;
    int high = len - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] <= mid) {
                cnt++;
            }
        }

        if (cnt <= mid) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    return low;
}

复杂度分析

• 时间复杂度：$O(nlogn)$，其中 $n$ 为 $\textit{nums}$ 数组的长度。二分查找最多需要二分 $O(logn)$ 次，每次判断的时候需要 $O(n)$ 遍历 $\textit{nums}$ 数组求解小于等于 $\textit{mid}$ 的数的个数，因此总时间复杂度为 $O(nlogn)$。
• 空间复杂度：$O(1)$。

方法八：位运算

具体证明及讲解可以参 @LeetCode-Solution 官方题解 。

简单来说，把数字转为二进制，那么其实只需要关注 $1$ 的个数及位数。具体到第 $i$ 位，我们统计 $\textit{nums}$ 数组中二进制展开后第 $i$ 位为 $1$ 的数为 $x$ 个，数字 $[1,n]$ 这 $n$ 个数二进制展开后第 $i$ 位为 $1$ 的数有 $y$ 个，那么很显然只有 $x > y$ 的情况下，重复的数的第 $i$ 位为 $1$。

分别把 $[1, n]$ 和数组数字的所有位为 $1$ 统计出来，然后按位还原，即可得到这个重复的数。

// Bit
public static int findDuplicate_bit(int[] nums) {
    int n = nums.length;
    int ans = 0;
    int bit_max = 31;
    while (((n - 1) >> bit_max) == 0) {
        bit_max -= 1;
    }

    for (int bit = 0; bit <= bit_max; ++bit) {
        int x = 0, y = 0;
        for (int i = 0; i < n; ++i) {
            if ((nums[i] & (1 << bit)) != 0) {
                x += 1;
            }
            if (i >= 1 && ((i & (1 << bit)) != 0)) {
                y += 1;
            }
        }
        if (x > y) {
            ans |= 1 << bit;
        }
    }

    return ans;
}

复杂度分析

• 时间复杂度：$O(nlogn)$，其中 $n$ 为 $\textit{nums}$ 数组的长度。$O(logn)$ 代表了我们枚举二进制数的位数个数，枚举第 $i$ 位的时候需要遍历数组统计 $x$ 和 $y$ 的答案，因此总时间复杂度为 $O(nlogn)$。

• 空间复杂度：$O(1)$。

方法九：双指针

具体讲解可以参考 官方题解 @kirsche 的题解 287.寻找重复数 。

简单来说，因为数组数字在 $[1, n]$，而数组索引值 $[0, n]$，那么数组就可以构成一个环形链表，我们可以使用 $\textit{nums}[\textit{nums}[i]]$ 来表示 $\textit{nums}[i]$.

那么问题就转化成了 142. 环形链表 II ，这里不多解释。

// Slow Fast Pointers
public static int findDuplicate_fastSlow(int[] nums) {
    int slow = 0;
    int fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\textit{nums}$ 数组的长度。
• 空间复杂度：$O(1)$。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗