数组缺失或重复元素（抽屉原理）

抽屉原理：即“一个萝卜一个坑”，8 个萝卜要放在 7 个坑里，则至少有 1 个坑里至少有 2 个萝卜。

前两天由于数组元素限定在数组长度的范围内，因此，我们可以通过一次遍历：

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

完全不使用额外空间的交换两个数，代码如下：

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];
}

如a与b进行交换，实现分析：

• 第一步 a ^= b 即 a = (a ^ b)；
• 第二步 b ^= a 即 b= b ^ ( a ^ b)，由于异或运算满足交换律，b ^ ( a ^ b) = b ^ b ^ a。由于一个数和自己异或的结果为 0 并且任何数与 0 异或都会不变的，所以此时 b 被赋上了 a 的值；
• 第三步 a ^= b 就是 a = a ^ b，由于前面二步可知 a = ( a ^ b)，b=a，所以 a = a ^ b 即 a = ( a ^ b ) ^ a。故 a 会被赋上 b 的值。

但是这种交换运算只是为了满足完全不使用额外空间，实际不推荐使用，注意一下几点：

• 对于异或运算实现的交换方法，如果调用 swap(nums, i, i)，那么最终的结果会变为 0，导致结果一直为 0 。
• 实际开发中一般不使用，为了性能丢失可读性，没有必要的。

1.找到所有数组中消失的数字（448 - 易）

题目描述：给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

示例 :

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

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

思路： 抽屉原理：我们可以使用原数组，通过自定义映射关系：元素i映射到下标i - 1的位置。遍历两遍数组：

• 建立映射：类似于每个元素 x 都有自己的位置 nums[x - 1] = x（这里x == nums[i]）.
• 寻找不符合映射的位置：存在空位置 i 就是说本来应该放在这个位置的元素 i + 1 消失了，记录并返回。

代码实现：

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            while (nums[nums[i] - 1] != nums[i]) {
                swap(nums, nums[i] - 1, i);
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

    private void swap(int[] nums, int i, int j) {
        if (i == j) return;
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}

2.数组中的重复数据（442-中）

题目描述：给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。要求：不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

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

思路：映射关系同上。不同点：最后加入结果的是重复元素。

• 一次遍历以后，那些“无处安放”的元素就是我们要找的“出现两次的元素”，没有映射成功，因为已经被占，所以在原位置。
• 在第二次遍历的时候，当出现这个坑的元素不对（无家可归），直接返回这个元素（重复的那个数）。

代码：

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            while (nums[nums[i] - 1] != nums[i]) {
                swap(nums, nums[i] - 1, i);
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                ans.add(nums[i]);
            }
        }
        return ans;
    }

    private void swap(int[] nums, int i, int j) {
        if (i == j) return;
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}

3.缺失的第一个正数（41-难）

题目描述：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例：

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

思路：本题的难点在于只使用常数时间复杂度，如使用额外空间或者排序，法1，法2，比较简单，但不符合题目要求。

法1：哈希表，将数组元素存入Set集合中（并记录数组的最大值），然后从1开始遍历，如果不存在，那么就是缺失的第一个正数。

法2：排序，遍历有序数组，用一个变量min记录最小值，如果与min相同，min++，否则跳过。

法3：原地哈希，思路同上。特别注意：本题数组元素大小没有限制在0~n之间，所以映射时注意索引nums[i]不要越界！

代码：

class Solution {
    // hash表
    public int firstMissingPositive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int large = 0;

        for (int num : nums) {
            if (num > large) {
                large = num;
            }
            set.add(num);
        }

        for (int i = 1; i <= large; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return large + 1;
    }

    // 排序
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int min = 1;

        for (int i = 0; i < n; i++) {
            if (nums[i] == min) {
                min++;
            }
        }
        return min;
    }

    // hash映射
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, nums[i] - 1, i);
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

    private void swap(int[] nums, int i, int j) {
        if (i == j) return;
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}

268. 丢失的数字

思路：后两种思路推荐！

• 排序 + 遍历（定义一个变量）
• hashset（两次遍历）

• 进行映射，丢失的数字没有映射上（抽屉原理）
• 下标与元素进行异或运算

class Solution {
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return 0;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    // 直接和下标进行异或运算，注意初始值为n
    public int missingNumber(int[] nums) {
        int ans = nums.length;
        for (int i = 0; i < nums.length; ++i) {
            ans ^= i ^ nums[i];
        }
        return ans;
    }
}