-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path136-Single Number.js
More file actions
72 lines (63 loc) · 1.67 KB
/
136-Single Number.js
File metadata and controls
72 lines (63 loc) · 1.67 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
* Problem link: https://leetcode.com/problems/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.
*
* NOTE: If there is only one unique number in an array, bitwise manipulation (XOR) can work
* Logic:
* A^A=0
* A^B^A=B
* (A^A^B) = (B^A^A) = (A^B^A) = B This shows that position doesn't matter.
*
* Solution: Bitwise manipulation
*/
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
var res = 0;
for (var i=0; i<nums.length ; i++)
{
res = res ^ nums[i];
}
return res;
};
/**
* Normally i would do like this,
* @param nums
* @returns {number}
*/
var singleNumberHash = function(nums) {
// worse
/*var hash = new Map();
for (let i=0; i<nums.length ; i++)
{
if (hash.has(nums[i])) {
hash.set(nums[i], hash.get(nums[i]) + 1);
} else {
hash.set(nums[i], 1);
}
}
for (let [key, value] of hash)
{
if (value === 1) {
return key;
}
}*/
// FAR MORE WORSE
var hash = [];
for (let i=0; i<nums.length ; i++)
{
if (hash[nums[i]]) {
delete hash[nums[i]];
} else {
hash[nums[i]] = 1;
}
}
return Object.keys(hash)[0];
};
console.log("result 1: ", singleNumber ([2,2,1])); // 1
console.log("result 2: ", singleNumber ([4,1,2,1,2])); // 4
console.log("result 2: ", singleNumber ([1])); // 1