【力扣刷题】只出现一次的数字

🔗 题目链接

题目描述

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

题目分析

方法一：暴力

这道题用暴力完全可以求解出来，两层循环，但是时间复杂度是O(n)。

或者，先对nums排序，这样时间复杂度是O(nlogn)。

方法二：hash表

还可以用hash表，遍历一遍nums，把每个数出现的次数记录在hash表中，然后从hash表中找出次数为1的那个数即可。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let hashMap = new Map();
  let count = 0;
  // 把每个数的次数记录到 map 中，key为该数，value为次数
  for (let i = 0; i < nums.length; ++i) {
    count = hashMap.get(nums[i]) || 0;
    hashMap.set(nums[i], count + 1);
  }
  // 遍历 map，找出次数为1的那个数
  for (let obj of hashMap) {
    if (obj[1] == 1) {
      return obj[0];
    }
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法三：位运算

什么是位运算？从现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。

口说无凭，举一个简单的例子来看下 CPU 是如何进行计算的，比如这行代码：

int a = 35;
int b = 47;
int c = a + b;
1
2
3

计算两个数的和，因为在计算机中都是以二进制来进行运算，所以上面我们所给的 int 变量会在机器内部先转换为二进制在进行相加：

35:  0 0 1 0 0 0 1 1
47:  0 0 1 0 1 1 1 1
————————————————————
82:  0 1 0 1 0 0 1 0
1
2
3
4

所以，相比在代码中直接使用(+、-、*、/)运算符，合理的运用位运算更能显著提高代码在机器上的执行效率。

现在，我们假设这个数组是nums=[3, 2, 1, 2, 3]，方便起见，我们就假设二进制位数最多只有4位。

1的二进制：0001
2的二进制：0010
3的二进制：0011
1
2
3

我们可以用如下表格来表示：

经过异或运算，我们发现，结果是0001，十进制也就是1。

题解代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let res = 0;
  for (let i = 0; i < nums.length; ++i) {
    res ^= nums[i];
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11

运行结果