抽屉原理：即“一个萝卜一个坑”，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; } }
