【力扣刷题】只出现一次的数字
🔗 题目链接
题目描述
给你一个 非空 整数数组 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];}}
};
方法三：位运算
什么是位运算？从现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态，计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。
口说无凭，举一个简单的例子来看下 CPU 是如何进行计算的，比如这行代码：
int a = 35;
int b = 47;
int c = a + b;
计算两个数的和，因为在计算机中都是以二进制来进行运算，所以上面我们所给的 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时，结果才为1 |
| | | 或 | 两个位都为0时，结果才为0 |
| ^ | 异或 | 两个位相同为0，相异为1 |
| ~ | 取反 | 0变1，1变0 |
| << | 左移 | 各二进位全部左移若干位，高位丢弃，低位补0 |
| >> | 右移 | 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
现在，我们假设这个数组是nums=[3, 2, 1, 2, 3]，方便起见，我们就假设二进制位数最多只有4位。
1的二进制：0001
2的二进制：0010
3的二进制：0011
我们可以用如下表格来表示：
| - | 第1位 | 第2位 | 第3位 | 第4位 |
|---|---|---|---|---|
| 3 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 1 |
| 异或运算 | 0 | 0 | 0 | 1 |
经过异或运算，我们发现，结果是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;
};
运行结果
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！