题目
题目
思路
- 暴力：两次循环
- 快排：O(nlgn)
- 哈希表：O(n)、O(n)
- 异或：
异或的性质：
- 交换律：可以任意交换运算因子，结果不变
- 结合律 (a^ b)^ c = a^ (b^ c)
- 对于任何数x，都有x^ x = 0, x^ 0 = x，同自己求异或运算为0，同0求异或运算为自己
- 自反性，A^ B^ B = A^ 0 = A
根据异或的自反性和交换律，由于只有一个数有一次且其他数都有且只有两次，不用思考算法进行时的中间结果，可以得到，如果将数组中的所有数都做异或，那么最终结果是那个只有一次的数
实现
异或
class Solution {
public int singleNumber(int[] nums) {
if (nums.length > 1) {
for (int i = 1;i < nums.length;i++) {
nums[0] ^= num[i];
}
}
return nums[0];
}
}
