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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 6k 阅读时长 ≈ 5 分钟

By Long Luo

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

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

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

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

因为题目要求：

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

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

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

方法一：排序

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

1
2
3
4
5
6
7
8
9
10
11
12
// 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)O(nlogn + n)，其中 nn 为 nums\textit{nums} 数组的长度，O(logn)O(logn) 排序复杂度，总时间复杂度为 O(nlogn+n)O(nlogn + n)。
  • 空间复杂度：O(logn)O(logn)，排序需要使用 O(logn)O(logn) 空间。

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

方法二：计数法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// 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)O(n)，其中 nn 为 nums\textit{nums} 数组的长度。
  • 空间复杂度：O(n)O(n)，需要新建一个长度为 nn 的数组。

方法三：HashSet

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

1
2
3
4
5
6
7
8
9
10
11
12
// 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)O(n)，其中 nn 为 nums\textit{nums} 数组的长度。
  • 空间复杂度：O(n)O(n)。

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

方法四：标记法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// 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)O(n)，其中 nn 为 nums\textit{nums} 数组的长度。
  • 空间复杂度：O(1)O(1)。

方法五：索引排序

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

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

  1. 如果 nums[i]==i+1\textit{nums}[i] == i + 1，说明已经排好序了，那么跳过，i++i++；
  2. 如果 nums[i]==nums[nums[i]−1]\textit{nums}[i] == \textit{nums}[\textit{nums}[i] - 1]，说明在正确的索引已经有一个值了，那么这个值就是重复的元素；
  3. 上述均不满足，交换 nums[i]\textit{nums}[i] 和 nums[nums[i]−1]\textit{nums}[\textit{nums}[i] - 1] 的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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)O(n)，其中 nn 为 nums\textit{nums} 数组的长度。
  • 空间复杂度：O(1)O(1)。

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

方法六：暴力2重循环

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

这个方法会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 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(n2)O(n^2)，其中 nn 为 nums\textit{nums} 数组的长度。
  • 空间复杂度：O(1)O(1)。

方法七：二分搜索

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 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)O(nlogn)，其中 nn 为 nums\textit{nums} 数组的长度。二分查找最多需要二分 O(logn)O(logn) 次，每次判断的时候需要 O(n)O(n) 遍历 nums\textit{nums} 数组求解小于等于 mid\textit{mid} 的数的个数，因此总时间复杂度为 O(nlogn)O(nlogn)。
  • 空间复杂度：O(1)O(1)。

方法八：位运算

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 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)O(nlogn)，其中 nn 为 nums\textit{nums} 数组的长度。O(logn)O(logn) 代表了我们枚举二进制数的位数个数，枚举第 ii 位的时候需要遍历数组统计 xx 和 yy 的答案，因此总时间复杂度为 O(nlogn)O(nlogn)。

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

方法九：双指针

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 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)O(n)，其中 nn 为 nums\textit{nums} 数组的长度。
  • 空间复杂度：O(1)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. 😉😃💗