只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
- 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 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
};
