Javascript O(n * log(n) + log(n)) solution ~O(n) memory


  • -2
    N
    var missingNumber = function(nums) {
    // This assumes mergesort O(n) mem and O(n log n) speed.
    // If quicksort is used then O(n^2) worst case speed O(n log n) average speed. O(log n) memory average O(n) worst case.
    nums.sort(function (a, b){
        return a-b;
    });
    var left = 0,
        right = nums.length - 1,
        mid = 0,
        val;
    while(left <= right){
        mid = Math.floor((left + right) / 2);
        val = nums[mid];
        if(mid === val){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return (left > right) ? left : right;
    };

  • 0
    Y

    The average speed of quick sort is O(nlogn).


  • 0
    N

    Sorry, yes I forgot, corrected.


Log in to reply
 

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