leetcode-136
date
‣
slug
leetcode-136
status
Published
tags
Leetcode
summary
type
Post
题目
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1示例 2:
输入: [4,1,2,1,2]
输出: 4来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/single-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析
我们这次先给出题解，再解释
class Solution { public int singleNumber(int[] nums) { int t = 0; for (int num : nums) { t = t ^ num; } return t; }}上述出现的符号 ^ 代表了 异或运算(XOR)
这个运算的特点是 同值取零 异值取一
有几个重要的法则
- 归零律： a ^ a = 0
- 恒等律： a ^ 0 = a
- 交换律： a ^ b ^ c = a ^ c ^ b
那么就很好解释了
我们从数组 nums 中取出一个 num 与 t 计算的值再赋给 t
例如对于数组[2, 2, 1]
相同数字异或全归为0
剩下 0 与 唯一数异或得到该数字
总结
位运算是一类很特别的题目，要多加反复练习