【前端算法】只出现一次的数字 II,位运算符：NOT，AND 和 XOR
【前端算法】只出现一次的数字 II,位运算符：NOT，AND 和 XOR
微芒不朽
发布于 2022-09-06 20:44:11
发布于 2022-09-06 20:44:11
只出现一次的数字 II
image
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
- 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出:3示例 2:
输入:[0,1,0,1,0,1,99]
输出:99解题思路
- 1.遍历输入数组，统计每个数字出现的次数，最后返回出现次数为 1 的数字。
- 2.位运算符：NOT，AND 和 XOR
解法一 统计次数+筛选
解法比较常规
- 1.统计每个元素出现的次数
- 2.找到只出现一次的元素；
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
var obj = {};
//1.统计每个元素出现的次数
for (var i = 0; i < nums.length; i++) {
var key = nums[i];
if (obj[key]) {
obj[key]++;
} else {
obj[key] = 1;
}
}
//2.找出只出现一次的元素
for (var k in obj) {
if (obj[k] === 1) {
return k
}
}
};解法二 位运算符求解
位运算符 | 价格 | 定义 |
|---|---|---|
与 | & | 两个位都为1，结果才为1，否则结果为0 |
或 | l | 两个位有一个为1，结果就是1，否则结果为0 |
非 | ~ | 如果位为0，结果是1，如果位为1，结果是0 |
异或 | ^ | 两个位相同结果为0，不同结果为1 |
举例
与&
与运算法则：两位同时为“1”，结果才为“1”，否则为0
5 & 1 = 1或|
或运算法则：两位其中一个为“1”，结果为“1”，否则为0
5| 1 = 5非
非运算法则：单目运算符
- 二进制原码：0000 0000 0000 0000 0000 0000 0000 0101
- 取反操作后：1111 1111 1111 1111 1111 1111 1111 1010 有符号整数都是用补码来 表示。补码=反码+1
- 1.先求反码：1000 0000 0000 0000 0000 0000 0000 0101
- 2.再求补码：1000 0000 0000 0000 0000 0000 0000 0110 最高位代表符号位 1 表示负数，0 表示正数
~5 = -6异或^
异或运算法则：两位不同，结果为“1”，否则为0 5^1 = 4
左移<<
左移运算法则：将数值向左移动若干位，用0补足 5<< 1 = 10
右移>>
右移运算法则：将数值向右移动若干位 5>>1 = 2
解题代码
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
var ones = 0,
twos = 0;
for (var i = 0; i < nums.length; i++) {
ones = ones ^ nums[i] & ~twos;
twos = twos ^ nums[i] & ~ones;
}
return ones
};
图片.png
本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-05，如有侵权请联系?cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录