711 字 9 分钟

本文最后更新于：4 个月前

看到今天的“每日一题”，第一时间发现用位运算很简单、快速。

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

题解思路

位运算

首先，来看个例子，比如：a^b
假设，a、b的值分别是15、2，
a 的值是15，转换成二进制为 1111，
b 的值是2，转换成二进制为 0010，
这下可以根据异或的运算规律，可以得出其结果为 1101，即13。

     1 1 1 1
⊕  0 0 1 0
————————————
     1 1 0 1

继续看看，我们可以来看看⊕的运算性质：

  • a⊕0 = a
  • a⊕a = 0
  • a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

继续看这道题，输入的数组一定是奇数个，
现在我假设一共有 2m+1 个元素，
其中，m对元素是成对出现的，唯一1个元素就是将被输出的结果。

接下来可以根据这个假设，列出这个表达式，
(a1⊕a2⊕⋯⊕am)⊕(a1⊕a2⊕⋯⊕am)⊕am+1
⇨ (a1​⊕a1​)⊕(a2​⊕a2​)⊕⋯⊕(am​⊕am​)⊕am+1​
⇨ 0⊕0⊕⋯⊕0⊕am+1​
⇨ am+1​

下面的代码就是采用按位异或操作符来完成的。

哈希表

成功提交后，我看了其他其他题解，大部分都是使用异或运算来完成。
但是，还有一些是使用哈希表来完成的。
对哦，为什么我不用 Hash 表呢？
因为我还不会 Hash 表啊hhh
好吧，不会归不会，但也得学学。

这里就直接小本本上记录两个使用Hash来实现的算法：

  1. 利用 Hash 表，Time: O(n)，Space: O(n)
  2. 解决方案：哈希集（HashSet）

代码

  • 使用位运算来完成。

    class Solution {
    public int singleNumber(int[] nums) {
        // (a1​⊕a1​)⊕(a2​⊕a2​)⊕⋯⊕(am​⊕am​)⊕am+1​
        // ⇨ 0⊕0⊕⋯⊕0⊕am+1​=am+1​
        // 结合三个性质：
        // 1、a⊕0 = a
        // 2、a⊕a = 0
        // 3、a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
        int key = 0;
        for(int num : nums){
            // 比如：a^b=13
            // a 的值是15，转换成二进制为1111，
            // b 的值是2，转换成二进制为0010，
            // 根据异或的运算规律，可以得出其结果为1101，即13
            key ^= num;
        }
        return key;
    }
}

    复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。因为只需要对数组遍历一次即可

  • 空间复杂度：O(1)

执行

 目录