Javascript: shouldn't this work?


  • 0
    M

    This is very frustrating. I get time limit exceeded so I don't know
    if this is algorithmically wrong or not.

    var singleNumber = function(nums) {
        if (nums.length === 1) return nums[0];
        
        for (var i=0;i<nums.length;i++) {
            if (i === nums.lastIndexOf(nums[i])) {
                return nums[i];
            }
        }
    };
    

    Javascript is much slower compared to java, c++. You can't
    really compare the solution to its java, c++ counterpart. I think
    the site should accomodate for this.


  • 0
    L

    lastIndexOf traverses the whole array backwards for the searched for number. To do this for each number in the array would not result in a linear runtime complexity (as the problem requests for).


  • 0
    I

    Your algorithm is actually correct, but it's not efficient. It runs O(n^2) because of the lastIndexOf function. If you use Set or Map, it could be O(n). However it doesn't need any extra space, which is the question asking for. If you use bit manipulation, you can easily reduce the run time to O(n) without using any extra space, below is the solution I found:

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

    It's because x ^ x = 0


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.