136. Single Number

🟢   🔖  位运算 数组  🔗 LeetCode

题目

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Each element in the array appears twice except for one element which appears only once.

题目大意

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求算法时间复杂度是线性的，并且不使用额外的辅助空间。

解题思路

• 可以使用位运算，利用异或运算的性质：任何一个数字异或它自己都等于 0 (x ^ x = 0)；
• 从头遍历数组，依次异或数组中的每一个数字；
• 数组中除了某个元素只出现一次以外，其余每个元素均出现两次，因为出现两次的数字在异或中会被抵消掉，所以最终得到的结果就是那个只出现一次的数字。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
	let res = 0;
	for (let i of nums) {
		res = res ^ i;
	}
	return res;
};

相关题目

相关题目

• 137. 只出现一次的数字 II
• 260. 只出现一次的数字 III
• 268. 丢失的数字
• 287. 寻找重复数
• 389. 找不同

- [137. 只出现一次的数字 II](https://leetcode.com/problems/single-number-ii)
- [260. 只出现一次的数字 III](https://leetcode.com/problems/single-number-iii)
- [268. 丢失的数字](https://leetcode.com/problems/missing-number)
- [287. 寻找重复数](https://leetcode.com/problems/find-the-duplicate-number)
- [389. 找不同](https://leetcode.com/problems/find-the-difference)