跳转至

面试题 16.01. 交换数字

题目描述

编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。

示例：

输入: numbers = [1,2]
输出: [2,1]

提示：

  • numbers.length == 2

解法

方法一：位运算

我们可以使用异或运算 \(\oplus\) 来实现两个数的交换。

异或运算有以下三个性质。

  • 任何数和 \(0\) 做异或运算，结果仍然是原来的数，即 \(a \oplus 0=a\)。
  • 任何数和其自身做异或运算，结果是 \(0\)，即 \(a \oplus a=0\)。
  • 异或运算满足交换律和结合律，即 \(a \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus 0=b\)。

因此，我们可以对 \(numbers\) 中的两个数 \(a\) 和 \(b\) 进行如下操作：

  • \(a=a \oplus b\)，此时 \(a\) 中存储了两个数的异或结果；
  • \(b=a \oplus b\)，此时 \(b\) 中存储了原来 \(a\) 的值；
  • \(a=a \oplus b\)，此时 \(a\) 中存储了原来 \(b\) 的值；

这样，我们就可以实现在不使用临时变量的情况下对两个数进行交换。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

1
2
3
4
5
6
class Solution:
    def swapNumbers(self, numbers: List[int]) -> List[int]:
        numbers[0] ^= numbers[1]
        numbers[1] ^= numbers[0]
        numbers[0] ^= numbers[1]
        return numbers

1
2
3
4
5
6
7
8
class Solution {
    public int[] swapNumbers(int[] numbers) {
        numbers[0] ^= numbers[1];
        numbers[1] ^= numbers[0];
        numbers[0] ^= numbers[1];
        return numbers;
    }
}

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {
        numbers[0] ^= numbers[1];
        numbers[1] ^= numbers[0];
        numbers[0] ^= numbers[1];
        return numbers;
    }
};

1
2
3
4
5
6
func swapNumbers(numbers []int) []int {
    numbers[0] ^= numbers[1]
    numbers[1] ^= numbers[0]
    numbers[0] ^= numbers[1]
    return numbers
}

1
2
3
4
5
6
function swapNumbers(numbers: number[]): number[] {
    numbers[0] ^= numbers[1];
    numbers[1] ^= numbers[0];
    numbers[0] ^= numbers[1];
    return numbers;
}

1
2
3
4
5
6
7
8
9
class Solution {
    func swapNumbers(_ numbers: [Int]) -> [Int] {
        var numbers = numbers
        numbers[0] ^= numbers[1]
        numbers[1] ^= numbers[0]
        numbers[0] ^= numbers[1]
        return numbers
    }
}

评论