面试题 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 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 |
|
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 |
|