javascriptarraysalgorithm

Get the first unique element from the array


I was solving the problem on LeetCode. i.e Single Number.

You need to create a function which takes a array as input and return the only element which is not repeated in array. The array will contain only one element like that.

[2,2,1] //1
[2,3,5,2,3] //5

I have solved the problem with the code below.

var singleNumber = function(nums) {
    let obj = {}  
    for(let a of nums){
        obj[a] = obj[a] + 1 || 1;
    }
    for(let key in obj){
        if(obj[key] === 1) return key;
    }
};

However after submitting the result it says

Runtime: 68 ms, faster than 72.96% of JavaScript online submissions for Single Number.

I am curious to know what is more efficient method for this problem.


Solution

  • The classical solution for non-repeating single number (where numbers are integers and repeated ones are repeated exactly once) is just computing the x-or of all of them:

    var singleNumber = function(nums) {
        let res = 0;
        for(let x of nums) res ^= x; // shorthand for res = res ^ x
        return res;
    };
    

    Note that if an explicit index-based for loop or a for-of or .forEach is faster or slower depends on the specific Javascript engine. For example:

    var singleNumber = function(nums) {
        let res = 0;
        for(let i=0,n=nums.length; i<n; i++) res ^= nums[i];
        return res;
    };
    

    may be faster than the for ... of approach.