136. Single Number
Linear Solution#
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
const map = {};
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
if (map[num] === 1) {
delete map[num];
} else {
map[num] = 1;
}
}
return Object.keys(map)[0];
};
Complexity#
- Time Complexity: O(N), where N is the size of
nums
.
- Space Complexity: O(N), where N is at maximum the size of
nums
/ 2.
Bit Manipulation Solution#
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let res = nums[0];
for (let i = 1; i < nums.length; i++) {
res = res ^ nums[i];
}
return res;
};
Complexity#
- Time Complexity: O(N), where N is the size of
nums
.
- Space Complexity: O(1).
All Solutions