Python with std library bisect_left (binary search), JS with my own Bin Srch


  • 0
    R
    class Solution(object):
        def lengthOfLIS(self, nums):
            minend = [0] * (len(nums))
            ln = 0
            for num in nums:
                i = bisect.bisect_left(minend, num, 0, ln)
                minend[i] = num
                if i == ln:
                    ln += 1
            return ln
    
    var lengthOfLIS = function(nums) {
        var minend = new Array(nums.length);
        minend.fill(0)
        var ln = 0
        nums.forEach(function(num) {
                var i = bs(minend, num, 0, ln)
                minend[i] = num
                if( i == ln) { 
                    ln += 1
                }
                
            
        })
        return ln
    };
    
    var bs = function(arr, num, start, end) {
        while (start < end) {
                var mid = start + ((end - start) /2) >> 0;
                if (arr[mid] < num) {
                    start = mid + 1
                }
                else {
                    end = mid
                }
            
        }
        return start
    }
    

Log in to reply
 

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