136. 只出现一次的数字

🟢   🔖  位运算 数组  🔗 力扣 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)；
• 从头遍历数组，依次异或数组中的每一个数字；
• 数组中除了某个元素只出现一次以外，其余每个元素均出现两次，因为出现两次的数字在异或中会被抵消掉，所以最终得到的结果就是那个只出现一次的数字。

复杂度分析

• 时间复杂度: O(n)，其中 n 为 nums 数组的长度，需要遍历数组中的所有整数。
• 空间复杂度: O(1)，使用了常数级别的辅助空间。

代码

/**
 * @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	丢失的数字	[✓]	位运算 数组 哈希表 3+
287	寻找重复数	[✓]	位运算 数组 双指针 1+
389	找不同		位运算 哈希表 字符串 1+
3158	求出出现两次数字的 XOR 值		位运算 数组 哈希表