方法三：如何用位运算（异或）在 O(N)/O(1) 下找出缺失的两个数？请解释“分组”的依据。

Method 3: How do you find the two missing numbers using bitwise XOR in O(N) time and O(1) space? Explain the grouping rationale.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

分类: Algorithms

标签: xor, lowbit, partition

参考答案摘要

答案 先计算 xorAll = (1^2^...^N) ^ (nums[0]^nums[1]^... )，得到 xorAll = a ^ b（a、b 为缺失数）。 因为 a != b，所以 xorAll 至少有一位为 1，取最低位 lowbit = xorAll & (-xorAll)（或找到任意为 1 的位）。 用 lowbit 将 1..N 与 nums 分成两组：该位为 1 的一组、为 0 ...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。