消失的数字

发表于 更新于 分类于 本文字数： 721 阅读时长 ≈ 1 分钟

题目描述

给定一个数组a[]，长度为n，保证1<=a[i]<=n,找出1-n中所有未出现的数字，不使用额外空间且时间复杂度为O(n).

思路分析

如果可以使用额外空间，我们会使用一块额外空间来记录某一个数字是否出现过，遍历一遍a来更新额外空间状态，然后遍历额外空间来获得未出现的数字。现在不允许使用额外空间，我们可以不可以直接在数组上来保存状态？可以这样做，假设数组长度为n，我们发现a[0]=3，那么说明3出现一次，由于数组下标是0~n-1，所以我们更新下标为2的值来表示3出现一次，怎么更新呢？直接让a[2]+n这样的话每次使用数组都要%n得到实际的值，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        // 完成此次循环后，nums[i]代表i+1出现的次数
        // 通过和将值和n比较，如果大于n说明有出现过i+1的值
        // 每次发现一个值，就－1然后和%n防止已经出现多次
        for (int i = 0; i != n; ++i) {
            nums[(nums[i] - 1) % n] += n;
        }
        for (int i = 0; i != n; ++i) {
            if (nums[i] <= n) {
                result.add(i + 1);
            }
        }
        return result;
    }
}