LeetCode 面试题 16.01. 交换数字

2025-12-19 HGNULB 约 7 分钟

文章信息 8 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 2-5 字节跳动亚马逊程序员面试金典（第 6 版）

题目描述

✅ 面试题 16.01. 交换数字

题意分析

输入是一个长度恰好为 2 的整型数组，要求把两个位置上的值互换，返回交换后的数组。功能本身是入门级的，题目真正加的限制是那句「不用临时变量」。

所以这题问的不是「怎么交换」，而是「在只有两个存储单元、不允许开第三个的前提下，怎么保证两个原始值都不丢」。一旦某一步把两个槽位都写成了同一个值，信息就永久损失，再也还原不回来。

约束信号：元素是 32 位有符号整数，正负都可能，可以取到边界值。这提示凡是引入加法或减法的方案都要先回答「会不会越界」，而位级别的运算天然没有这个顾虑。

边界要过一遍：两个数相等（此时交换是恒等操作，但过程中间会不会把值抹成零？）；一正一负；其中一个是最小值或最大值；以及题目虽然保证长度为 2，但如果把它写成通用的「交换下标 $i$ 和 $j$」，$i$ 与 $j$ 相同这一情形必须单独想清楚。

解法：异或交换

核心思路

最自然的写法是引入临时变量 t = a; a = b; b = t;，一共三次赋值，但第三个存储单元正是题目禁止的东西，直接出局。

瓶颈很清晰：两个槽位要装下两个值，任何一步覆盖写入都会毁掉一个值，除非被覆盖的那个值还能从剩下的内容里反推出来。于是问题转化为——找一个二元运算 $f$，使得从 $\big(f(a,b),\,b\big)$ 能唯一还原出 $a$，从 $\big(f(a,b),\,a\big)$ 也能唯一还原出 $b$。

加法满足这个要求：a = a + b; b = a - b; a = a - b;。但和可能超出 32 位范围，在会做溢出检查或把溢出定义为未定义行为的语言里不可用，得额外解释一句才安全。异或则更干净：它满足 $x \oplus x = 0$、$x \oplus 0 = x$，并且可交换、可结合，逐位独立不产生进位，因此对任意 32 位整数都不会溢出，本身就是自己的逆运算。

于是维持这条不变量：三步的每一步执行完毕后，两个槽位合起来仍然携带原始 $a$ 与 $b$ 的完整信息。 初始是 $(a,\,b)$；第一步后是 $(a\oplus b,\;b)$，用它异或 $b$ 就能还原 $a$；第二步后是 $(a\oplus b,\;a)$，因为 $b \oplus (a \oplus b) = a$；第三步后是 $(b,\;a)$，因为 $(a\oplus b) \oplus a = b$。三步走完，交换完成，全程没有第三个变量。

解题步骤

第一步 numbers[0] ^= numbers[1]，把两数的异或和存进 0 号槽。为什么不怕丢失：1 号槽仍是原始的 $b$，而异或和配上 $b$ 足以还原 $a$，信息量没有减少。

第二步 numbers[1] ^= numbers[0]，此时 1 号槽变成 $b \oplus (a \oplus b)$。为什么它等于 $a$：异或满足结合律与交换律，式子可重排为 $a \oplus (b \oplus b) = a \oplus 0 = a$。

第三步 numbers[0] ^= numbers[1]，0 号槽变成 $(a \oplus b) \oplus a$。为什么它等于 $b$：同理重排为 $b \oplus (a \oplus a) = b \oplus 0 = b$。注意这一步用的是已经被改写过的 1 号槽，顺序不能调换。

直接返回原数组。为什么不必新建数组：三步都是原地写入，原数组已经是答案。

以 numbers = [1, 2] 走一遍：初始二进制为 $a=01_2$、$b=10_2$。第一步 numbers[0] = 01_2 \oplus 10_2 = 11_2 = 3，数组变成 [3, 2]。第二步 numbers[1] = 10_2 \oplus 11_2 = 01_2 = 1，数组变成 [3, 1]，可以看到 1 号槽已经拿回了原始的 $a=1$。第三步 numbers[0] = 11_2 \oplus 01_2 = 10_2 = 2，数组变成 [2, 1]，正是交换后的结果。

再用两数相等的 numbers = [5, 5] 验一遍这个写法不会翻车：第一步得 $5 \oplus 5 = 0$，数组 [0, 5]；第二步得 $5 \oplus 0 = 5$，数组 [0, 5]；第三步得 $0 \oplus 5 = 5$，数组 [5, 5]。中间虽然出现了 0，但 1 号槽始终保有一份原值，信息没丢，结果正确。

代码实现

// 重点处理空输入、边界下标、重复元素和结果更新时机，避免漏掉极端用例。
class Solution {
    public int[] swapNumbers(int[] numbers) {
        numbers[0] ^= numbers[1];
        numbers[1] ^= numbers[0];
        numbers[0] ^= numbers[1];
        return numbers;
    }
}

// 重点处理空输入、边界下标、重复元素和结果更新时机，避免漏掉极端用例。
func swapNumbers(numbers []int) []int {
    numbers[0] ^= numbers[1]
    numbers[1] ^= numbers[0]
    numbers[0] ^= numbers[1]
    return numbers
}

复杂度分析

时间复杂度：$O(1)$，凭据：无论输入取什么值，都只执行固定的三次异或赋值，没有任何循环或递归。

空间复杂度：$O(1)$，凭据：全部写入都发生在入参数组的两个槽位上，没有申请任何额外存储，这正是题目要考的点。

关键点总结

异或的四条性质要能随口说出：$x\oplus x=0$、$x\oplus 0=x$、可交换、可结合。本题以及一大批位运算题的推导都只用到这四条，把它们当公理用就能把式子化开。

「不许用临时变量」的本质是「不许损失信息」。凡是遇到这类限制，就去找一个可逆的合成运算，把两份数据压进一个槽再逐步解出来，这个思路在原地反转、原地去重里同样成立。

异或相比加减法的优势是逐位独立、不产生进位，因此绝不溢出。选运算时先看值域，这个判断在跨语言写代码时尤其重要。

中间过程出现 0 不代表信息丢了。判断一个原地技巧是否安全，要看「两个槽位合起来能否还原原始输入」，而不是看某一个槽位当前长什么样。

面试视角：这题几乎必然被追问「如果 $i=j$ 会怎样」。异或交换在自己和自己交换时会把该元素清零，所以在通用的 swap(arr, i, j) 里必须先判 i != j；主动说出这一点，比写对三行代码更能证明你理解了原理。

面试视角：真实工程里应当直接用临时变量。异或交换可读性差、对编译器优化不友好，现代编译器对三行临时变量交换生成的机器码往往更优。能指出「这是面试题技巧而非生产实践」，通常是加分项而不是扣分项。

易错点总结

错误写法：把三步的顺序写成 a ^= b; a ^= b; b ^= a;。用例 [1, 2] → 前两步互相抵消使 a 回到 1，第三步得到 b = 2 ^ 1 = 3，结果是 [1, 3]，两个值都错。三步中被写入的槽位必须按「0 号、1 号、0 号」交替。

错误写法：把它抽成通用函数 swap(arr, i, j) 却不判断 i != j。用例 i = j = 0 → 第一步 arr[0] ^= arr[0] 直接把该元素清成 0，后续两步都在 0 上运算，元素永久丢失。

错误写法：认为两数相等时结果会被清零，于是加一条 if (numbers[0] == numbers[1]) return numbers; 的特判。用例 [5, 5] → 特判本身不产生错误答案，但它说明没理解「清零的根源是两个操作数指向同一个存储位置，而不是数值相等」，面试中一被追问就会露馅。

错误写法：改用 a = a + b; b = a - b; a = a - b; 并声称与异或等价。用例两个元素都取 $2^{31}-1$ → 和达到 $2^{32}-2$，在把有符号溢出定义为未定义行为的 C/C++ 里是未定义行为，在带溢出检查的语言里直接抛异常；异或版本则对任意取值都安全。

错误写法：偷偷用临时变量 int t = numbers[0]; 完成交换。用例任意输入 → 判题系统会通过，但题目明确写了不许用临时变量，面试场景下等同于没答上来。

错误写法：新建一个数组 return new int[]{numbers[1], numbers[0]};。用例任意输入 → 返回值虽然对，却额外开了 $O(1)$ 之外的存储且没有原地修改入参，同样绕过了考点。

错误写法：把异或和加法混写成 numbers[0] ^= numbers[1] + 1 之类，误判运算符优先级。用例 [1, 2] → 在 Java 中 + 的优先级高于 ^，实际算的是 1 ^ 3 = 2，整条还原链立刻断掉，后两步得到的都是垃圾值。

错误写法：用 numbers[0] = numbers[0] ^ numbers[1] 之后又去读一个提前缓存好的旧值，例如先 int old = numbers[0]; 再在第三步用 old。用例 [1, 2] → 第三步算的是 $1 \oplus 1 = 0$，得到 [0, 1]，缓存的旧值和「不用临时变量」的前提自相矛盾。

错误写法：以为负数参与异或需要额外处理符号位。用例 [-1, 2] → 补码表示下 $-1$ 是全 1，$-1 \oplus 2$ 得到 $-3$，第二步 $2 \oplus (-3) = -1$，第三步 $(-3) \oplus (-1) = 2$，结果 [2, -1] 完全正确；异或是逐位操作，与数值的符号解释无关，多加分支只会引入 bug。

错误写法：忘了返回值，只做原地修改就结束函数。用例任意输入 → 本题签名要求返回 int[]，漏掉 return numbers; 会返回空引用导致判题失败。

相似题目

题目	难度	考察点
136. 只出现一次的数字	简单	用 $x\oplus x=0$ 抵消成对元素
260. 只出现一次的数字 III	中等	靠异或和的最低位 1 把元素分成两组
268. 丢失的数字	简单	下标与值一起异或，抵消后剩缺失值
371. 两整数之和	中等	异或作无进位加法，与运算左移作进位
面试题 05.06. 整数转换	简单	异或得差异位，再数 1 的个数
面试题 05.07. 配对交换	简单	掩码分离奇偶位后各自移位再合并
面试题 16.07. 最大数值	简单	同样禁用判断语句，改用符号位构造选择
面试题 17.04. 消失的数字	简单	要求线性时间常数空间，异或是标准答案