Swift solution - DP & Binary Search


  • 0
    class Solution {
        func lengthOfLIS_DP(_ nums: [Int]) -> Int {
            if nums.count == 0 {
                return 0
            }
            
            var dp = [Int](repeatElement(0, count: nums.count))
            var length = 0
            
            for num in nums {
                var i = 0
                var j = length
                while i != j {
                    let m = (i + j) / 2
                    if dp[m] < num {
                        i = m + 1
                    } else {
                        j = m
                    }
                }
                dp[i] = num
                length = max(i + 1, length)
            }
            
            return length
        }
        
        func lengthOfLIS_BinarySearch(_ nums: [Int]) -> Int {
            var tails = [Int](repeatElement(0, count: nums.count))
            var length = 0
            
            for num in nums {
                var left = 0
                var right = length
                var middle = 0
                while left != right {
                    middle = (left + right) / 2
                    if tails[middle] < num {
                        left = middle + 1
                    } else {
                        right = middle
                    }
                }
                tails[left] = num
                if left == length {
                    length += 1
                }
            }
            
            return length
        }
    }
    

Log in to reply
 

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