LeetCode 面试题 16.01. 交换数字

约 3 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 程序员面试金典（第 6 版） 字节 亚马逊
标签
数学 位运算

题目描述

✅ 面试题 16.01. 交换数字

image-20260928231050763

题意分析

在长度恰好为二的数组中原地交换两个整数，不借助额外临时变量。操作的是下标 0、1 两个不同的存储位置，数值可以相等，也可以为负。

解法：异或交换

核心思路

[!blue]

异或满足交换律和结合律，并且 x ^ x = 0、x ^ 0 = x。所以把两个值异或后，只要再异或其中一个原值，就能抵消它并还原另一个值。

用 a、b 表示两个位置最初的值。第一步让第零项异或第一项，状态变为 (a ^ b, b)：第零项保存两者混合的信息，第一项仍保留原来的 b。

第二步用第一项异或更新后的第零项，得到 b ^ (a ^ b) = a，状态变为 (a ^ b, a)。第三步用第零项异或更新后的第一项，得到 (a ^ b) ^ a = b，最终状态就是 (b, a)。

每一步都依赖另一个位置当前保存的值，三个操作必须依次完成。即使原值相等，第一步把第零项变成零时，第一项仍保留原值，后续照样可以还原。负数也只是固定宽度的位模式，异或的抵消规律同样成立，不需要额外处理符号。

解题步骤

  1. 执行 numbers[0] ^= numbers[1]，将两个原值的异或结果保存在第零项。
  2. 执行 numbers[1] ^= numbers[0]，消去原来的第二项，恢复原来的第一项。
  3. 再执行 numbers[0] ^= numbers[1]，消去原来的第一项，恢复原来的第二项。
  4. 返回已经原地交换的输入数组。

代码实现

class Solution {
    public int[] swapNumbers(int[] numbers) {
        // 第一步把第零项变成两数异或，第一项仍保留原 b。
        numbers[0] ^= numbers[1];
        // 第二步消去原 b，第一项还原为原 a。
        numbers[1] ^= numbers[0];
        // 第三步消去原 a，第零项还原为原 b，交换完成。
        numbers[0] ^= numbers[1];

        return numbers;
    }
}

func swapNumbers(numbers []int) []int {
    // 第一步把第零项变成两数异或，第一项仍保留原 b。
    numbers[0] ^= numbers[1]
    // 第二步消去原 b，第一项还原为原 a。
    numbers[1] ^= numbers[0]
    // 第三步消去原 a，第零项还原为原 b，交换完成。
    numbers[0] ^= numbers[1]
    return numbers
}

复杂度分析

  • 时间复杂度：$O(1)$，固定执行三次异或赋值。
  • 空间复杂度：$O(1)$，直接修改输入数组，没有额外临时变量或新数组。

关键点总结

[!green]

  • 一个位置保存异或结果，另一个位置保存可用于抵消的原值。
  • 三步分别完成混合、还原第一项、还原第二项。
  • 相同数值不影响正确性，但两个存储位置必须不同。

易错点总结

[!yellow]

  • 连续两次异或更新同一侧，会撤销前一步，无法完成规定的还原过程。
  • 只执行前两步就返回，仍有一个位置保存着异或结果。
  • 把这一做法用于同一个位置与自身交换，会在第一步清零；本题的两个固定下标不存在这种别名问题。

相似题目

题目 难度 关联与区别
136. 只出现一次的数字 简单 相同值异或抵消是三次异或交换的代数基础，原题用它消去成对元素。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/27940327
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！