mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
30 lines
1.4 KiB
Markdown
Executable File
30 lines
1.4 KiB
Markdown
Executable File
# [136. Single Number](https://leetcode.com/problems/single-number/)
|
||
|
||
## 题目
|
||
|
||
Given a **non-empty** array of integers, every element appears *twice* except for one. Find that single one.
|
||
|
||
**Note:**
|
||
|
||
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
|
||
|
||
**Example 1:**
|
||
|
||
Input: [2,2,1]
|
||
Output: 1
|
||
|
||
**Example 2:**
|
||
|
||
Input: [4,1,2,1,2]
|
||
Output: 4
|
||
|
||
## 题目大意
|
||
|
||
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求算法时间复杂度是线性的，并且不使用额外的辅助空间。
|
||
|
||
|
||
## 解题思路
|
||
|
||
- 题目要求不能使用辅助空间，并且时间复杂度只能是线性的。
|
||
- 题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。于是最终做法是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。**利用的性质是 x^x = 0**。
|