leetcode 442

题目

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1]
输出：[]

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

分析

这道题目如果没有空间复杂度要求的话不算很难，但是仅使用常量额外空间难度还是很大的。

一个很容易的想法就是开辟一个新的数组或者map，然后来计数，最差的情况下需要O(n)的额外空间，这可能是大部分人的想法。

下面两个高赞回答

方法1

function findDuplicates(nums) {
    let result = [];
    for (let i = 0; i < nums.length; i++) {
        let num = Math.abs(nums[i]);
        if (nums[num - 1] > 0) {
            nums[num - 1] *= -1;
        } else {
            result.push(num);
        }
    }
    return result;
};

它是利用了输入数组，把数组里面的内容融入了一个二进制信息，例如41和-41，41的信息没有丢失，但是却同时融入进去了一个布尔值信息！，这样就可以把输入数组同时存储输出结果数组所需要的标记信息

方法2

/**
     * 这个题属于技巧题 首先仔细看输入的给定的数组值 该值的区间为 1 ≤ a[i] ≤ n
     * 这其实是这道题解题的关键点，好好利用这个信息。 某些元素出现了两次，
     * 而一些其他的元素只出现了1次，我们可以利用这些元素在出现次数上面的不一样做文章。
     *
     * 仔细观察发现1 ≤ a[i] ≤ n 这个条件，正好和我们数组的下标差1，我们可以按照数值
     * 来遍历数组，那么在数组中具有相同值的元素，会被经过两次，那么我们只要想出一种方式
     * 在这个遍历结束后可以区分，哪些元素被经过了多次即可，由于数组元素具有1 ≤ a[i] ≤ n
     * 这样的范围，那其实我们当每次经过一个元素时，给他加上n，当遍历结束时，我们再次遍历数组
     * 那些数值超过2n的元素索引+1，对应的就是我们的出现了两次的元素。
     * @param nums
     * @return
     */
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ret = new ArrayList<>();

        int n = nums.length;
        for(int i = 0; i < n; i++){
            nums[(nums[i] - 1) % n] += n;
        }

        for(int i = 0; i < n; i++){
            if(nums[i] > 2 * n) ret.add(i+1);
        }
        return ret;
    }

这段代码主要是看到了1 ≤ a[i] ≤ n 这个条件，保证每个地方的数值+n不会导致和原有的信息的值域发生冲突，不会发生信息的丢失，例如在取出nums[(nums[i] - 1) % n]时做了一个取余的操作，用取余操作提取原本的数字，用除法操作提取出现次数，因此是编码了两个int数值，本质上和Math.abs的操作一样，在更加丰富的信息中找到原来的数字。

空间利用

上述的两个操作让我不禁想到，如何榨干空间利用率？上述的方法是否具有通用性？

(1) 经过分析，想达到上面需要满足条件

元素的取值范围有限

例如在[1,10]，或者只在正数中取值

因此，我们看题是需要额外关注这个看起来不起眼的取值范围，很可能就是突破口

(2) 满足条件之后，如何向数组中编码更多的信息？

首要考虑的因素自然是保证原先的数字不丢失，理论上来说，对于取值范围range，可编码的数字范围为$len(R)/range$，其中R是所有实数集合。

例如对x>0的数值编码，只能编入一个布尔值，对应上述方法1的操作；对0<x<100的数值编码，需要把低两位保存，高位乘以100，对应的千位之上的数字就是新加入的信息，取余就是原始信息，对应上述方法2的操作。