灯的个人博客

forever young,forever weeping.

0%

初级算法-只出现一次的数字

发表于 更新于 分类于

题目

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

说明：

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

示例 1:

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

示例 2:

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

题解

常规set

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
28
function singleNumber(nums: number[]): number {
  let numSet: Set<number> = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (numSet.has(nums[i])) {
      numSet.delete(nums[i]);
    } else {
      numSet.add(nums[i]);
    }
  }
  return [...numSet][0];
}
``` 

位运算
- 1 ^ 1 = 0
- 0 ^ 1 = 1;
- 1 ^ 1 ^ 2 = 2;
- 2 ^ 2 ^ 1 = 1
- 相同的数字或运算等于0,0与人气其他数字或运算等于此数字
- 2 ^ 2 ^ 3 ^ 3 ^ 1 =  1
```typescript
function singleNumber(nums: number[]): number {
  let result = 0;
  for (let i = 0; i < nums.length; i++) {
    result ^= nums[i];
  }
  return result;
}

参考链接