找出只存在一次的数字

该类型问题，主要从异或、二进制位、位操作考虑

找出一个数组中只出现一次的数字，其他数字存在 2 次

方法 1：使用异或运算符

异或，通俗的讲为找不同，将数转为二进制，然后对每位上取不同

示例：1 ^ 2 = 3;

因为

1 -> 01
2 -> 10

所以1 ^ 2 = 11，等于十进制的 3

异或特点

• 两个数相同，结果为 0，反之为 1
• 任何数与 0 异或，结果为任何数
• 满足交换律：a ^ b ^ c === a ^ c ^ b

var singleNumber = function (nums) {
    let x;
    for (let i = 0; i < nums.length; i++) {
        x ^= nums[i];
    }
    return x;
};

方法 2：对数组排序，然后找出索引 i 不等于 i + 1，也不等于 i - 1 的元素

找出数组中 2 个只出现一次的数字，其他数字存在 2 次

方法 1：使用异或运算符

数组示例：[2, 2, 3, 3, 5, 6]

解释

• 首先将数组的所有值异或在一起得到 5 和 6 异或的结果，即2^2^3^3^5^6 = 3
• 然后找到 3 二进制位第一个为 1 的位置，因为异或的性质是相异为 1，那么如果按照这个二进制位对数组进行分组，那么 5 和 6 必然被分开了
• 3 的二进制中第一位就是 1，那么我们按这个条件进行分组，第一位二进制位为0：{2,2,6}；第一位二进制位为1：{3,3,5}，最后将这两组数分别异或并输出就可以得到结果了

function find_num(arr) {
    //  记录数组所有值的异或结果
    let ret = 0;
    //  记录 ret 二进制中第一个为 1 的位置
    let pos = 0;
    //  记录分组后异或结果的输出
    let x = 0;
    let y = 0;
    //  获取所有值异或结果
    for (let i = 0; i < arr.length; i++) {
        ret ^= arr[i];
    }
    //  找到 ret 二进制中第一个为 1 的位置
    for (let i = 0; i < 32; i++) {
        //  将 ret 进行右移 i 位，然后和 1 进行与运算
        //  &：按位与运算，每一个比特位，两个位置都为 1，结果为 1，反之为 0
        if (1 === ((ret >> i) & 1)) {
            pos = i;
            break;
        }
    }
    //  对源数组进行分组输出异或结果
    for (let i = 0; i < arr.length; i++) {
        //  将数组每一项进行 pos 位的右移操作，然后和 1 进行与运算
        if (1 === ((arr[i] >> pos) & 1)) {
            x ^= arr[i];
        } else {
            y ^= arr[i];
        }
    }
    return [x, y];
}

方法 2：利用 js 对象属性唯一性，将数组数据转为对象属性进行操作

function searchNum(arr) {
    let obj = {};
    let result = [];
    for (let i = 0; i < arr.length; i++) {
        if (obj[arr[i]]) {
            obj[arr[i]]++;
        } else {
            obj[arr[i]] = 1;
        }
    }
    for (let prop in obj) {
        if (obj[prop] === 1) {
            result.push(prop);
        }
    }
    return result;
}

方法 3：利用 indexOf 与 lastIndexOf

function searchNum2(arr) {
    let result = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr.indexOf(arr[i]) === arr.lastIndexOf(arr[i])) {
            result.push(arr[i]);
        }
    }
    return result;
}

找出数组中 3 个只出现一次的数字，其他数字存在 2 次

数组示例：[1, 2, 3, 4, 4, 5, 5]

思路：先找出 3 个数字中的一个，然后就变成了找 2 个数字的问题了

• 全数组进行异或，得到1^2^3 = 0
• 定义一个函数 f(n)，找出 n 的二进制中的最后一位 1，其他位都改为 0（如 6 的二进制 0110，因此 f(6) = 2（0010））
• 0^1、0^2、0^3得到的结果中，只有一个数字的二进制的第 m 位为 1，所以可以找到该数字

找出一个数组中只出现一次的数字，其他数字存在 3 次

方法 1：先排序，然后再遍历一次

方法 2：二进制位、位操作

思路：从二进制表示的角度，每个位上的 1 加起来，应该是可以被 3 整除的，但是多了一个 x

• 如果可以被 3 整除，则说明 x 该位置为 0
• 如果不能被 3 整除，则说明 x 该位置为 1

function findNum(arr) {
    const length = arr.length;
    let m = [];
    let result = [];
    let num = 0;
    for (let i = 0; i < 32; i++) {
        for (let j = 0; j < length; j++) {
            let bit = arr[j] & 1;
            if (!m[i]) {
                m[i] = [];
            }
            m[i] = Number(m[i]) + bit;
            arr[j] >>= 1;
        }
    }
    console.log(m);
    for (let i = 0; i < 32; i++) {
        if (m[i] % 3 != 0) {
            result.push(i);
            num += 1 << (i & 0x1f);
        }
    }
    for (let i = 0; i < result.length; i++) {
        num += result[i] << 1;
    }
    if (result[0] === 0) {
        num += 1;
    }
    return num;
}
console.log(findNum([4, 4, 4, 5, 5, 5, 9]));