使用 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。