使用 JavaScript 解答 LeetCode 第 136 题,只出现一次的数字,简单难度。

题目

原题链接

本题目是 LeetCode 题库第 136 题,由此访问。

题目描述

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

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

示例 1:

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

示例 2:

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

解题

AC 样例

var singleNumber = function(nums) {
  let result = 0;
  nums.forEach(num => result ^= num);
  return result;
};

解题思路

该题目有多种解决方法,常用方法有栈存储方法、哈希表存储方法等。其基本逻辑都是遍历当前数据,并在新设存储结构中进行统计,最终获得结果。

上文解题采用位计算方法进行解答,利用异或计算(XOR)的特性,对相同数据进行抵消。其具体方法是将数据遍历并进行累计异或计算,异或计算对同一数据的计算结果为 0,即相互抵消,其结果不影响后续计算。在全部数据被遍历一次后,其他出现两次的数据均已被抵消,仅剩的数据即是只出现一次的数据。

知识点

位操作是 JavaScript 标准操作符的一种,一般分为位计算符号和位操作符号。在一个计算式中出现位操作符时,原数据将转为 32 位二进制数进行计算,超出 32 位的部分将被舍弃。

位计算符包含:按位与(and, &)、按位或(or, |)、按位非(not, ~)和按位异或(xor, ^);位操作符包含:左移(<<)、右移(>>)、无符号右移(>>>)。

异或计算的基本原则是相同数据计算值为 0,否则为 1,连续异或计算遵守交换律,可以任意更换计算位置。任意数 x 与 0 进行异或计算的值为 x,任意数 x 与 -1 进行异或计算的值为 ~x。