「力扣」第 442 题:数组中重复的数据

liweiwei1419 ... 2022-1-6 位运算
  • 位运算
About 5 min

# 题目描述

给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 一次两次 。请你找出所有出现 两次 的整数,并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例 1:

输入:nums = [4,3,2,7,8,2,3,1]
输出:[2,3]
1
2

示例 2:

输入:nums = [1,1,2]
输出:[1]
1
2

示例 3:

输入:nums = [1]
输出:[]
1
2

提示:

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • nums 中的每个元素出现 一次两次

# 特别注意:基于“异或运算”交换两个变量的值,这种操作仅仅只是用于解题,千万不要在工作中使用这样的代码,会有一些坑,重点是:使得代码难以阅读和被他人理解。没有必要为了节约空间去牺牲代码的可读性。

#

方法:“抽屉原理” + 基于“异或运算”交换两个变量的值

思路分析:“桶排序”的思想是“抽屉原理”,即“一个萝卜一个坑”,8 个萝卜要放在 7 个坑里,则至少有 1 个坑里至少有 2 个萝卜。

“抽屉原理”的思想很简单,但是借助它我们可以完成一些比较难的问题,例如:「力扣」第 41 题:缺失的第一个正数(困难) (opens new window)。还有一个与本题(标注为“中等”)类似的问题:「力扣」第 448 题: 找到所有数组中消失的数字(简单) (opens new window),就很神奇,同样是“抽屉原理”,可以解决的问题涵盖了“简单”、“中等”、“困难”三个等级。

这里由于数组元素限定在数组长度的范围内,因此,我们可以通过一次遍历:

  • 让数值 1 就放在索引位置 0 处;
  • 让数值 2 就放在索引位置 1 处;
  • 让数值 3 就放在索引位置 2 处;

……

一次遍历以后,那些“无处安放”的元素就是我们要找的“出现两次的元素”。

为了不使用额外的空间,这里使用到的一个技巧是“基于异或运算交换两个变量的值”:交换两个整数,除了引入一个新的变量,写出一个“轮换”的赋值表达式以外,还有两种比较 tricky 的做法,下面给出结论。

“异或运算”是不进位的二进制加法,它有如下性质:

如果 a ^ b = c ,那么 a ^ c = bb ^ c = a 同时成立,利用这一条,可以用于交换两个变量的值。

于是,交换两个变量的值,例如 ab,不使用第三个变量,有两种不同的方法:

基于异或运算 基于加减法
a = a ^ b
b = a ^ b
a = a ^ b
a = a + b
b = a - b
a = a - b

我理解的方式就是自己在纸上写几个例子,并且记住这个结论。个人觉得“基于异或运算”交换两个变量的值好记一些,因为右边都一样,左边依次是 aba

在这里特别感谢用户 @davidlaid 给出的意见:

  • 对于异或运算实现的交换方法,如果调用 swap(nums, i, i),那么最终的结果会变为 0
  • 对于加减法实现的交换方法,有可能发生溢出。

调用 swap(nums, i, i),那么最终的结果会变为 0 这是因为,如果是在数组中,自己和自己交换,只有 1 个空间,这个数会在异或运算的过程中变为 0,因此单独判断一下就好了。我个人还是比价少用这个技巧的,如果题目中限制了不能使用额外的存储空间,才用“基于异或运算实现的交换方法”。

参考代码

注意:因为这里数组的数值和索引有一个偏差,所以我将交换数组元素的方法做了一个封装,这样可以降低编码出错的概率,供大家参考。

调用 swap 方法使用了栈空间,但是如果不这么写,代码很容易出错,也不符合编码规范,我个人觉得知道这个知识点就可以了。

还是强调两点:

1、上面介绍的通过异或运算交换两个变量的做法,不要在平常工程当中用,节约不了多少空间

2、尽量抽取方法以体现主干逻辑,尽管不符合本题意思。

写代码性能虽然很重要,但在很多时候,为了一点点性能,丢失可读性是没有必要的。

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        for (int i = 0; i < len; i++) {
            while (nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] - 1 != i) {
                res.add(nums[i]);
            }
        }
        return res;
    }

    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        nums[index1] = nums[index1] ^ nums[index2];
        nums[index2] = nums[index1] ^ nums[index2];
        nums[index1] = nums[index1] ^ nums[index2];
    }
}
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
27
28
29
30
31
32
33

复杂度分析

  • 时间复杂度:O(N)O(N),这里 NN 是数组的长度。
  • 空间复杂度:O(1)O(1),这里因为使用异或运算交换数组的元素,故没有使用额外的数组空间。
Last update: January 14, 2022 00:24
Contributors: liweiwei1419