LeetCode笔记：只出现一次的数字

#leetcode

问题

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

说明：

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

示例 1:

输入: [2,2,1]

输出: 1

示例  2:

输入: [4,1,2,1,2]

输出: 4

解法一

思路：

利用 js 对象 key 值不能重复的原理，统计出每个数字的出现个数，然后再找出只出现一次的数字，需要两次循环。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  const obj = {};

  //统计每个数字的出现次数
  nums.forEach((item) => {
    if (!(item in obj)) {
      obj[item] = 1;
    } else {
      obj[item] += 1;
    }
  });

  //取出出现一次的数字
  for (let i in obj) {
    if (obj[i] === 1) {
      return i;
    }
  }
  return 0;
};

解法二

思路：

运用按位异或的特性来求解，一次遍历。

  1. 满足交换律：a ^ b ^ c <=> a ^ c ^ b
  2. 任何数和 0 异或为任何数：0 ^ n => n
  3. 相同的数异或为 0：n ^ n => 0

所以假设 nums 为[4,1,2,1,2]

4 ^ 1 ^ 2 ^ 1 ^ 2

等价于

4 ^ 1 ^ 1 ^ 2 ^ 2

等价于

4 ^ 0 ^ 0

等价于

4

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let result = nums[0];

  // XOR
  nums.forEach((item, i) => {
    if (i !== 0) {
      result = result ^ item;
    }
  });

  return result;
};

同类型解决方案的问题请参考

LeetCode 笔记: 找不同

参考

评论