136. 只出现一次的数字

发表于 分类于 阅读次数：

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

说明：

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

示例 1：

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

示例 2：

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

循环(二分法)查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  nums.sort((a, b) => a - b);
  let i = 0;
  let j = nums.length - 1;
  while (i < j) {
    let mid = (j + i) / 2;
    if (nums[mid] !== nums[mid - 1]) {
      if (mid % 2 === 0) {
        i = mid;
      } else {
        j = mid - 1;
      }
    }
    if (nums[mid] !== nums[mid + 1]) {
      if (mid % 2 === 0) {
        j = mid;
      } else {
        i = mid + 1;
      }
    }
  }
  return nums[i];
};

对象唯一属性

1
2
3
4
5
6
7
8
9
10
11
12
13
var singleNumber = function (nums) {
  let obj = {};
  for (let i = 0; i < nums.length; i++) {
    if (obj[nums[i]]) {
      delete obj[nums[i]];
    } else {
      obj[nums[i]] = true;
    }
  }
  for (let key in obj) {
    return key;
  }
};

但题目中要求时间复杂度 O(n)，空间复杂度是 O(1)，看了题解，答案是使用位运算。对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。

  1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
  2. 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
  3. 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b

异或预算

1
2
3
var singleNumber = function (nums) {
  return nums.reduce((x, y) => x ^ y);
};