题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/single-number著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：列表操作

算法

  1. 遍历 nums 中的每一个元素
  2. 如果某个 nums 中的数字是新出现的，则将它添加到列表中
  3. 如果某个数字已经在列表中，删除它

    1. class Solution(object):
    2. def singleNumber(self, nums):
    3.     """
    4.     :type nums: List[int]
    5.     :rtype: int
    6.     """
    7.     no_duplicate_list = []
    8.     for i in nums:
    9.         if i not in no_duplicate_list:
    10.             no_duplicate_list.append(i)
    11.         else:
    12.             no_duplicate_list.remove(i)
    13.     return no_duplicate_list.pop()

复杂度分析

  • 时间复杂度：O(n),我们遍历 nums 花费 O(n) 的时间。我们还要在列表中遍历判断是否存在这个数字，花费 O(n)的时间，所以总循环时间为 O(n).
  • 空间复杂度：O(n) 。我们需要一个大小为 n 的列表保存所有的nums 中元素。

方法 2：哈希表

算法

  1. 我们用哈希表避免每次查找元素是否存在需要的 O(n)时间。
  2. 遍历 nums 中的每一个元素
  3. 查找hash_table 中是否有当前元素的键
  4. 如果没有，将当前元素作为键插入 hash_table
  5. 最后， hash_table 中仅有一个元素，用 popitem 获得它

    1. class Solution(object):
    2. def singleNumber(self, nums):
    3.     """
    4.     :type nums: List[int]
    5.     :rtype: int
    6.     """
    7.     hash_table = {}
    8.     for i in nums:
    9.         try:
    10.             hash_table.pop(i)
    11.         except:
    12.             hash_table[i] = 1
    13.     return hash_table.popitem()[0]

复杂度分析

  • 时间复杂度：O(n⋅1)=O(n) 。for 循环的时间复杂度是 O(n) 的。Python 中哈希表的 pop 操作时间复杂度为O(1)
  • 空间复杂度： O(n) 。hash_table 需要的空间与nums 中元素个数相等。

方法 3：数学

概念
2 * (a + b + c) - (a + a + b + b + c) = c2∗(a+b+c)−(a+a+b+b+c)=c

  1. class Solution(object):
  2.    def singleNumber(self, nums):
  3.        """
  4.        :type nums: List[int]
  5.        :rtype: int
  6.        """
  7.        return 2 * sum(set(nums)) - sum(nums)

复杂度分析

  • 时间复杂度：O(n + n) = O(n) 。sum 会调用 next 将 nums 中的元素遍历一遍。我们可以把上述代码看成 sum(list(i, for i in nums)) ，这意味着时间复杂度为 O(n)，因为 nums 中的元素个数是 n 个。
  • 空间复杂度：O(n+n)=O(n) 。 set 需要的空间跟 nums 中元素个数相等。

方法 4：位操作

概念
如果我们对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位
a⊕0=a
如果我们对相同的二进制位做 XOR 运算，返回的结果是 0
a⊕a=0
XOR 满足交换律和结合律
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
所以我们只需要将所有的数进行 XOR 操作，得到那个唯一的数字。

  1. class Solution(object):
  2.    def singleNumber(self, nums):
  3.        """
  4.        :type nums: List[int]
  5.        :rtype: int
  6.        """
  7.        a = 0
  8.        for i in nums:
  9.            a ^= i
  10.        return a

复杂度分析

  • 时间复杂度： O(n)。我们只需要将nums 中的元素遍历一遍，所以时间复杂度就是 nums 中的元素个数。
  • 空间复杂度：O(1) 。

针对第四种方式，位运算 做以下回顾：

Java位运算-回顾

计算机的存储都是二进制，而且都是补码。

为什么按照补码存储？

  • 计算机内部都是二进制存储（代表高低电位，也可理解为正负极电位）
  • 为了方便表示正负数，规定：最高位为0表示正数，最高位为1表示负数
  • 原码就是真值的二进制形式，正数的补码、反码、补码都一样，负数的反码就是除符号位的其他位取反，故为反码，负数的补码是反码的末尾位加1的结果，即补码=反码+1
  • 无符号数没有原码、反码和补码一说。只有带符号数才存在不同的编码方式。也可以理解为补码存储就是为了方便处理负数
  • 使用补码可以将符号位和其他位统一处理，同时，减法也可以按加法来处理，即如果是补码表示的数，不管是加减法都直接用加法运算即可实现，简化了计算
  • 两个用补码表示的数相加时，如果最高位（符号位）有进位，则进位被舍弃
  • 使符号位能与有效值部分一起参加运算，从而简化运算规则。从而可以简化运算器的结构，提高运算速度
  • 加法运算比减法运算更易于实现。使减法运算转换为加法运算，进一步简化计算机中运算器的线路设计

    那么，人们为什么想到了用补码，反码这种东西？

    因为“模”，举个例子：时钟，时钟转一圈又回到原点，所以时钟是12进制，12点即是0点。
    于是：10点调整到5点
    可以是，往前转5个小时： 10-5=5
    也可以是，往后转7个小时：10+7=12+5=5
    这个概念，数学中叫作：“同余”，即两整数A、B用同一个正整数M (M称为模)去除而余数相等，则称A、B对M同余，记作：
    A＝B (MOD M)
    具有同余关系的两个数为互补关系，其中一个称为另一个的补码。当M＝12时，－5和＋7，－4和＋8，－3和＋9就是同余的，它们互为补码。

从同余的概念和上述时钟的例子，不难得出结论：对于某一确定的模，用某数减去小于模的另一个数，总可以用加上“模减去该数绝对值的差”来代替。因此，在有模运算中，减法就可以化作加法来做。

可以看出，补码的加法运算所依据的基本关系为：
[x]补+ [y]补= [x+y]补
补码减法所依据的基本关系式：
[x-y]补 =[x+(-y)]补= [x]补+ [-y]补
至于加法运算为什么比减法运算易于实现以及CPU如何实现各种算术运算等问题，则需要通过对数字电路的学习来理解CPU的运算器的硬件实现问题的相关内容了。

是不是太秀了！省略一万个。。。。

原码 反码 补码

原码

将一个数字转换成二进制就是这个数值的原码。

  1. int a = 5; //原码  0000 0000 0000 0101
  2. int b = -3;//原码  1000 0000 0000 0011
  4. //扩展：java的进制转换
  5. @Test
  6. public void 进制转换(){
  7.     System.err.println("十进制转二进制 "+Integer.toBinaryString(10));
  8.     System.err.println("十进制转八进制 "+Integer.toOctalString(10));
  9.     System.err.println("十进制转十六进制 "+Integer.toHexString(10));
  11.     System.err.println("二进制转十进制 "+Integer.valueOf("1010",2));
  12.     System.err.println("八进制转十进制 "+Integer.valueOf("12",8));
  13.     System.err.println("十六进制转十进制 "+Integer.valueOf("a",16));
  14.     //---输出如下：
  15.     //十进制转二进制 1010
  16.     //十进制转八进制 12
  17.     //十进制转十六进制 a
  18.     //二进制转十进制 10
  19.     //八进制转十进制 10
  20.     //十六进制转十进制 10
  21. }

反码

分两种情况：正数和负数

  • 正数 正数的反码就是原码。
  • 负数 负数的反码是在原码的基础上，符号位不变 其它位都取反。

    1. 5 的原码：0000 0000 0000 0101
    2. -3 的原码：1000 0000 0000 0011
    3. -3 的反码：1111 1111 1111 1100

补码

仍然分正数和负数两种情况

  • 正数 正数的补码就是原码。
  • 负数 负数的补码在反码的基础上加1。

    1. 5 的补码：0000 0000 0000 0101
    2. -3 的反码：1111 1111 1111 1100
    3. -3 的补码: 1111 1111 1111 1101

计算机在进行数值运算的时候，是通过补码表示每个数值的。
比如

  1. 5 - 3 = 5 + ( -3 )
  2. 相当于 
  3.     0000 0000 0000 0101 
  4.  +  1111 1111 1111 1101
  5.  =1 0000 0000 0000 0010

最后的结果是1 0000 0000 0000 0010 这样的二进制，由于 int 类型只有 4 byte，所以最高位产生了溢出，进位 1 被丢弃。结果就变成了 0010 也就是 2，5 - 3 = 2 没有毛病。
数组-找出数组中出现一次的数 - 图1

Java提供的位运算符有：

  • 左移( << )：向左移动n位低位补0，即乘 2
  • 右移( >> )：向右移动n位高位补0，即除2

  • 无符号右移( >>> ):向右移动n位，忽略符号位，空位都以0补齐

  • 位与( & ) ：如果相对应位都是1，则结果为1，否则为0

  • 位或( | )：如果相对位有一个1，则结果为1，否则为0

  • 位异或( ^ )：如果相对位值不同，则结构为1，否则为0

  • 位非( ~ )：按位取反，0变1，1变0

  • 除了位非( ~ )是一元操作符外，其它的都是二元操作符。

    左移<<

  1. System.out.println(5<<2);//运行结果是20
  2. 5转换为二进制补码，int默认8字节也就是32位长度，如下
  3. 0000 0000 0000 0000 0000 0000 0000 0101           
  4. 然后左移2位后，低位补0：
  5. 0000 0000 0000 0000 0000 0000 0001 0100           
  6. 换算成10进制为20
  8. @Test
  9. public void 左移() {
  10.     //1010
  11.     //101000
  12.     System.out.println(Integer.toBinaryString(10));
  13.     System.out.println(Integer.toBinaryString(10<<2));
  14.     //11111111111111111111111111110110
  15.     //11111111111111111111111111011000
  16.     System.out.println(Integer.toBinaryString(-10));
  17.     System.out.println(Integer.toBinaryString(-10<<2));
  18. }

右移>>>

  1. System.out.println(5>>2);//运行结果是1
  2. 还是先将5转为2进制表示形式：
  3. 0000 0000 0000 0000 0000 0000 0000 0101 
  4. 然后右移2位，高位补0：
  5. 0000 0000 0000 0000 0000 0000 0000 0001
  6. 换算为10进制为1
  8.  @Test
  9. public void 右移() {
  10.     System.out.println(Integer.toBinaryString(10));
  11.     System.out.println(Integer.toBinaryString(10>>2));
  12.     //1010
  13.     //10
  15.     System.out.println(Integer.toBinaryString(-10));
  16.     System.out.println(Integer.toBinaryString(-10>>2));
  17.     //11111111111111111111111111110110
  18.     //11111111111111111111111111111101
  20. }

无符号右移>>>

  1. System.out.println(5>>3);//结果是0
  2. System.out.println(-5>>3);//结果是-1
  3. System.out.println(-5>>>3);//结果是536870911
  5. 5换算成二进制： 0000 0000 0000 0000 0000 0000 0000 0101
  6. 5右移3位后结果为0，0的二进制为： 0000 0000 0000 0000 0000 0000 0000 0000  // (用0进行补位)
  7. -5换算成二进制： 1111 1111 1111 1111 1111 1111 1111 1011
  8. -5右移3位后结果为-1，-1的二进制为： 1111 1111 1111 1111 1111 1111 1111 1111  // (用1进行补位)
  9. -5无符号右移3位后的结果 536870911
  10. 换算成二进制： 0001 1111 1111 1111 1111 1111 1111 1111   // (用0进行补位)
  14. @Test
  15. public void 无符号右移() {
  16.     System.out.println(Integer.toBinaryString(10));
  17.     System.out.println(Integer.toBinaryString(10>>>2));
  18.     //1010
  19.     //10
  21.     System.out.println(Integer.toBinaryString(-10));
  22.     System.out.println(Integer.toBinaryString(-10>>>2));
  23.     //11111111111111111111111111110110
  24.     //111111111111111111111111111101
  25. }

位与&

  1. System.out.println(5 & 3);//结果为1
  3. 5转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
  4. 3转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
  5. -------------------------------------------------------------------------------------
  6. 1转换为二进制：0000 0000 0000 0000 0000 0000 0000 0001
  8. @Test
  9. public void 位与() {
  10.     System.out.println(Integer.toBinaryString(10));
  11.     System.out.println(Integer.toBinaryString(3));
  12.     System.out.println(Integer.toBinaryString(10&3));
  13.     //1010
  14.     //11
  15.     //10
  16. }

位或|

  1. System.out.println(5 | 3);//结果为7
  2. 5转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
  3. 3转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
  4. -------------------------------------------------------------------------------------
  5. 7转换为二进制：0000 0000 0000 0000 0000 0000 0000 0111
  7. @Test
  8. public void 位或() {
  9.     System.out.println(Integer.toBinaryString(10));
  10.     System.out.println(Integer.toBinaryString(3));
  11.     System.out.println(Integer.toBinaryString(10|3));
  12.     //1010
  13.     //11
  14.     //1011
  15. }

位异或 ^

  1. System.out.println(5 ^ 3);//结果为6
  3. 5转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
  4. 3转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
  5. -------------------------------------------------------------------------------------
  6. 6转换为二进制：0000 0000 0000 0000 0000 0000 0000 0110
  8. @Test
  9. public void 异或() {
  10.     System.out.println(Integer.toBinaryString(10));
  11.     System.out.println(Integer.toBinaryString(3));
  12.     System.out.println(Integer.toBinaryString(10^3));
  13.     //1010
  14.     //11
  15.     //1001
  16. }

位非~

  1. System.out.println(~5);//结果为-6
  2. 5转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
  3. -------------------------------------------------------------------------------------
  4. -6转换为二进制：1111 1111 1111 1111 1111 1111 1111 1010
  6. @Test
  7. public void 位非() {
  8.     System.out.println(Integer.toBinaryString(10));
  9.     System.out.println(Integer.toBinaryString(~10));
  10.     //1010
  11.     //11111111111111111111111111110101
  12. }
  • 由位运算操作符衍生而来的有：
  • &= 按位与赋值
  • |= 按位或赋值
  • ^= 按位非赋值

  • = 右移赋值

  • = 无符号右移赋值

  • <<= 赋值左移
  • 和 += 一个概念而已。

    题目意义

    教会我们使用位运算，编程中可以尝试使用
    ps：我tm写那么多年代码了，一次也没用过位运算，估计用在项目组，没人看的懂，还会被骂垃圾代码
    总结：这tm是用来秀的！