Last active
March 10, 2018 19:42
-
-
Save vadimkorr/ebab34afd3dc453bedb11f6704111ad6 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Task: Given array of size 2*N-1, containing N-1 pairs of same integers and one unique integer. | |
// Find unique integer without sorting array - it's too big | |
// Complexity: O(n) | |
let findUnique = function(lst) { | |
let map = new Map(); | |
lst.forEach((id) => { | |
if (map.has(id)) map.delete(id); | |
else map.set(id, 1); | |
}) | |
for (let id of map.keys()) { | |
if (map.get(id) === 1) return id; | |
} | |
} | |
let arr = [1, 1, 5, 7, 8, 5, 100, 9, 7, 8, 9]; | |
console.log(findUnique(arr)); // 100 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment