Swift solution - MergeSort, BinarySearchTree, BinarySearch


  • 0
    class Solution {
        func countSmaller_MergeSort(_ nums: [Int]) -> [Int] {
            var result = [Int]()
            var counts = [Int](repeatElement(0, count: nums.count))
            var indexes = [Int]()
            
            for i in 0..<nums.count {
                indexes.append(i)
            }
            mergeSort(nums, 0, nums.count - 1, &indexes, &counts)
            for i in 0..<counts.count {
                result.append(counts[i])
            }
            
            return result
        }
        
        private func mergeSort(_ nums: [Int], _ start: Int, _ end: Int, _ indexes: inout [Int], _ counts: inout [Int]) {
            if end <= start {
                return
            }
            
            let middle = start + (end - start) / 2
            mergeSort(nums, start, middle, &indexes, &counts)
            mergeSort(nums, middle + 1, end, &indexes, &counts)
            
            merge(nums, start, end, &indexes, &counts)
        }
        
        private func merge(_ nums: [Int], _ start: Int, _ end: Int, _ indexes: inout [Int], _ counts: inout [Int]) {
            let middle = start + (end - start) / 2
            var left = start
            var right = middle + 1
            var rightCount = 0
            var newIndexes = [Int](repeatElement(0, count: end - start + 1))
            var sortIndex = 0
            
            while left <= middle && right <= end {
                if nums[indexes[right]] < nums[indexes[left]] {
                    newIndexes[sortIndex] = indexes[right]
                    rightCount += 1
                    right += 1
                } else {
                    newIndexes[sortIndex] = indexes[left]
                    counts[indexes[left]] += rightCount
                    left += 1
                }
                sortIndex += 1
            }
            while left <= middle {
                newIndexes[sortIndex] = indexes[left]
                counts[indexes[left]] += rightCount
                left += 1
                sortIndex += 1
            }
            while right <= end {
                newIndexes[sortIndex] = indexes[right]
                sortIndex += 1
                right += 1
            }
            for i in start...end {
                indexes[i] = newIndexes[i - start]
            }
        }
        
        func countSmaller_BinarySearchTree(_ nums: [Int]) -> [Int] {
            var result = [Int](repeatElement(0, count: nums.count))
            var root: BinarySearchTreeNode? = nil
                
            for i in stride(from: nums.count - 1, through: 0, by: -1) {
                root = insert(nums[i], root, &result, i, 0)
            }
            
            return result
        }
        
        private func insert(_ num: Int, _ node: BinarySearchTreeNode?, _ result: inout [Int], _ i: Int, _ preSum: Int) -> BinarySearchTreeNode {
            var node = node
            
            if node == nil {
                node = BinarySearchTreeNode(num, 0)
                result[i] = preSum
            } else if node!.val == num {
                node?.duplicate += 1
                result[i] = preSum + node!.sum
            } else if node!.val > num {
                node!.sum += 1
                node!.left = insert(num, node!.left, &result, i, preSum)
            } else {
                node!.right = insert(num, node?.right, &result, i, preSum + node!.duplicate + node!.sum)
            }
            
            return node!
        }
        
        func countSmaller_BinarySearch(_ nums: [Int]) -> [Int] {
            let count = nums.count
            var result = [Int](repeatElement(0, count: count))
            var sorted = [Int]()
            
            for i in stride(from: count - 1, through: 0, by: -1) {
                let index = binarySearch(&sorted, nums[i])
                result[i] = index
                sorted.insert(nums[i], at: index)
            }
            
            return result
        }
        
        private func binarySearch(_ nums: inout [Int], _ target: Int) -> Int {
            if nums.count == 0 {
                return 0
            }
            
            var start = 0
            var end = nums.count - 1
            
            if nums[end] < target {
                return end + 1
            }
            if nums[start] >= target {
                return 0
            }
            while start + 1 < end {
                let middle = start + (end - start) / 2
                if nums[middle] < target {
                    start = middle + 1
                } else {
                    end = middle
                }
            }
            if nums[start] >= target {
                return start
            }
            
            return end
        }
    }
    
    class BinarySearchTreeNode {
        var left: BinarySearchTreeNode? = nil
        var right: BinarySearchTreeNode? = nil
        var val = 1
        var sum = 1
        var duplicate = 1
        
        public init(_ val: Int, _ sum: Int) {
            self.val = val
            self.sum = sum
        }
    }
    

Log in to reply
 

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