136. Single Number
136. Single Number
题目
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](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)