原地寻找数组中重复/消失的数字

有一类题目，如果不考虑时间和空间复杂度，会超级的简单；但是如果要求时间复杂度为O(n)，空间复杂度为O(1)的话，就会变得有点麻烦

这里面有两个技巧，如果掌握了，也就没有那么麻烦了 (目前只发现了两个技巧，如果后续后其它技巧，可补充！！)

这类题有一个特点：数组的长度为n，且范围为[0, n-1]或者[1, n]

众神归位法

哈哈哈，这个名字是突然想到的，感觉很好玩！！

该方法是基于上述介绍的那个特点：数组的长度为n，且范围为[0, n-1]或者[1, n]

简单来说，就是把数组中的每个数都按照下标存放，即：下标i的地方放元素i

对于寻找「重复」的数字，如果下标i的地方已经是元素i了，此时再来了一个i，肯定就重复了

对于寻找「消失」的数字，如果下标i的地方不是元素i了，肯定就缺少了

下面给出核心代码：


public void find(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 只有 nums[i] != i 才需要归位
        while (nums[i] != i) {
            // 如果没有该判断，可能会出现死循环
            if (nums[i] == nums[nums[i]]) break;
            // 交换 nums[i] 和 nums[nums[i]]
            int t = nums[i];
            nums[i] = nums[t];
            nums[t] = t;
        }
    }
}

负数标记法

如果不考虑空间复杂度，我们完全可以定义一个长度为n的标记数组vis[]，如果元素i出现了，就把数组相应下标置为true

现在要求空间复杂度O(1)，所以显然上述思路不行，但是我们可以曲线救国

如果原数组的范围是[1, n]，那么如果元素i出现了，我们可以把下标为i的元素 (✖️-1)，变相标记了一波

细心的人可能发现了，我这里说的范围是[1, n]，对于范围[0, n-1]，元素0✖️-1，还是0，无法标记，所以不可以 ❌

题目实战

数组中重复的数字

题目详情可见数组中重复的数字


xxxxxxxxxx
public int findRepeatNumber(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) return nums[i];
            int t = nums[i];
            nums[i] = nums[t];
            nums[t] = t;
        }
    }
    return -1;
}

找到所有数组中消失的数字

题目详情可见找到所有数组中消失的数字

这里给出两种方法！！


x
// 众神归位法
// 由于范围是 [1, n]，所以需要向左偏移一位
public List<Integer> findDisappearedNumbers(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] - 1 != i) {
            if (nums[i] == nums[nums[i] - 1]) break;
            int t = nums[i];
            nums[i] = nums[t - 1];
            nums[t - 1] = t;
        }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] - 1 != i) ans.add(i + 1);
    }
    return ans;
}

// 负数标记法
public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[Math.abs(nums[i]) - 1] > 0) {
            nums[Math.abs(nums[i]) - 1] *= -1;
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) res.add(i + 1);
    }
    return res;
}

数组中重复的数据

题目详情可见数组中重复的数据


xxxxxxxxxx
public List<Integer> findDuplicates(int[] nums) {
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        nums[Math.abs(nums[i]) - 1] *= -1;
        if (nums[Math.abs(nums[i]) - 1] > 0) ans.add(Math.abs(nums[i]));
    }
    return ans;
}