645. Set Mismatch

645. Set Mismatch

[TOC]

题目内容

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]
Example 2:

Input: nums = [1,1]
Output: [1,2]  

Constraints:

2 <= nums.length <= 104
1 <= nums[i] <= 104

思路

很容易想到[排序]和[哈希表]的方法, 但是用[位运算]能实现时间复杂度O(n)、空间复杂度O(1)的算法

位运算

1. 在让 nums 和 1..n 共 2n个数字中, 缺失的数字出现1次, 重复的数字出现3次
2. 将 nums 和 1..n 这2n个数字依次异或, 得到的结果是 x ^ y
3. lowbit=xor & (−xor)，则 lowbit 为 x 和 y 的二进制表示中的最低不同位,
4. 根据 lowbit 可以将上诉 2n 个数字分为2组, x y 分别在这两组中

class Solution {
	public int[] findErrorNums(int[] nums) {
		int n = nums.length;
		int x = 0;
		for (int i : nums) {
			x = x ^ i;
		}

		for (int i = 1; i <= n; i++) {
			x = x ^ i;
		}

		int f = x & (-x);

		int nums1 = 0;
		int nums2 = 0;

		for (int i : nums) {
			if ((i & f) == 0) {
				nums1 = nums1 ^ i;
			} else {
				nums2 = nums2 ^ i;
			}
		}

		for (int i = 1; i <= n; i++) {
			if ((i & f) == 0) {
				nums1 = nums1 ^ i;
			} else {
				nums2 = nums2 ^ i;
			}
		}

		for (int i : nums) {
			if(nums1 == i) {
				return new int[]{nums1, nums2};
			}
		}
		return new int[]{nums2, nums1};
	}
}

收获

1. 异或运算 ⊕满足交换律和结合律，且对任何数字 aa 都满足 a⊕a=00 和 0⊕a=a; 因此 xor=x⊕x⊕x⊕y=x⊕yxor=x⊕x⊕x⊕y=x⊕y，即 xx 和 yy 的异或运算的结果。
2. lowbit=xor & (−xor)，则 lowbit为 xx 和 yy 的二进制表示中的最低不同位,
3. 只有一个数字重复或缺失的题目可以考虑用异或解决

参考

官方题解