LeetCode 136. 只出现一次的数字

今天的力扣每日一题,因为位运算是我的短板之一,这题我没解出来,最终看了题解,不得不说妙啊,记录一下。

题目描述

  • 136. 只出现一次的数字

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

  • 难度:简单

说明

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

示例 1

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

示例 2

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

题解

说实话,刚看这道题的时候,我就想到几种方法:

  • 两重循环,外层 $i = 0 到 n$ ,内层 $j = i 到 n$ 。循环 $(1+n)*n/2$ 次,时间复杂度为 $o(n^2)$ ,怎么说呢,显然不是线性复杂度。
  • 开多一个 List 来存每个数字出现的次数,好吧,不能使用额外空间

反正我是没想出来,看看官方的题解:

首先我们要用到位运算 异或 ,也就是 ⊕ ,它具有以下三个性质:

  1. 任何数与它本身异或结果为 0,即 $a \oplus a = 0$;
  2. 任何数与 0 异或结果为它本身,即 $0 \oplus a = a$;
  3. 异或运算满足交换律和结合律,即 $a \oplus b \oplus a = b \oplus a \oplus a = b \oplus (a \oplus a) = b \oplus 0 = b$;

假如我们对数组中所有数做异或运算,因为满足交换律,我们总可以把两两相同的数字交换到一起,并通过结合律运算为 0,最终只剩下 0 与那个唯一的数字做异或运算,剩下那个唯一的数。

woc 就这么简单,看来位运算还是学的不太好,有必要花点时间研究一下了。

  • 语言:C++
1
2
3
4
5
6
7
8
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto e: nums) ret ^= e;
return ret;
}
};

结果

我感觉这个用时有点不正常,不过看了下更快速的提交代码,都是一样的啊,估计是电脑问题吧。