数组缺失或重复元素（抽屉原理）
2021-05-30 本文已影响0人
_code_x
抽屉原理：即“一个萝卜一个坑”，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;
}
}
