在 Java 基础中,我们最容易忽视的就是位运算符,而在位运算符中最容易忽视的就是异或运算符。今天遇到一道算法题就吃了亏,所以打算利用这道算法题学习一下异或运算符。
1. 算法题
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1] |
示例 2:
输入: [4,1,2,1,2] |
这就是我遇到的一道算法题,有兴趣可以先做一做再往下看。
2. 异或运算符概述
异或运算符是对二进制的运算符。参与运算的两个值,如果两个相应bit位相同,则结果为0,否则为1。
例子:
161 ^ 6 = 167 |
看起来好像没什么用,但是异或运算有三个很重要的规律:
// 1.如果我们对 0 和二进制位做 XOR(异或) 运算,得到的仍然是这个二进制位 |
3. 排序法解题
上面的算法题有多种解法,区别在于性能的优劣。在这里我就讲两种解法,排序法和异或运算法。
为什么要讲排序法呢,因为这是我的第一个答案,也是比较容易的解法(除了穷举法,性能太低基本不考虑):
public static int singleNumber(int[] nums) { |
通过16个测试用例:
语言 | 执行用时 | 内存消耗 |
---|---|---|
Java | 4 ms | 42.3 MB |
4. 异或运算法解题
根据题目描述 “除了某个元素只出现一次以外,其余每个元素均出现两次。” 结合异或运算的规律,我们只需要将所有的数进行 XOR 操作,得到那个唯一的数字。
例子:
参数:[4, 1, 2, 1, 2] |
public int singleNumber(int[] nums) { |
通过16个测试用例:
语言 | 执行用时 | 内存消耗 |
---|---|---|
Java | 1 ms | 42 MB |
相比排序法要快了整整 3 ms,如果要处理巨大的数据量位运算就凸显了十分明显的优势。