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

只出现一次的数字 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

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