有意思的算法题

题目描述

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

// 1、维护一个对象来记录每一个元素出现的次数。使用元素的值作为key,元素出现的次数作为value。遍历这个对象，找到value为1的key。
function singleNumber(nums) {
  const obj = {};
  for (let i = 0; i < nums.length; i++) {
    obj[nums[i]] = obj[nums[i]] ? obj[nums[i]] + 1 : 1;
  }
  for (let key in obj) {
    if (obj[key] === 1) {
      return Number(key); // 由于 key 是 string ,因此我们这里需要转化下
    }
  }
}
console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8])); // 8
// 2、不使用额外空间。异或操作。两个相同的数字进行异或操作结果是0。
function singleNumber(nums) {
  for (let i = 1; i < nums.length; i++) {
    nums[0] ^= nums[i];
  }
  return nums[0];
};
console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8])); // 8
复制代码

附： 1、& 按位与

&是二元运算符,对应的位都为1结果是1，任意一个位是0 则结果是0。
复制代码

2、| 按位或

任一个操作数为1 那么结果就是1
复制代码

3、^ 按位异或

两个操作位都为1的话，结果产生0
复制代码

4、~ 按位非

加1->取反
复制代码

5、>> 右移

2048>>10 => 2048/2^10 // 2
复制代码

6、<< 左移

2<<10 => 2 * 2^10 // 2048
复制代码

转载于:https://juejin.im/post/5c33079be51d45522435d638