【前端算法】只出现一次的数字 II,位运算符：NOT，AND 和 XOR

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

说明：

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

示例 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
};

本文使用 mdnice 排版