Swift solution - Merge Sort


  • 0
    class Solution {
        func reversePairs(_ nums: [Int]) -> Int {
            var helper = [Int](repeatElement(0, count: nums.count))
            var nums = nums
            
            return mergeSort(0, nums.count - 1, &nums, &helper)
        }
        
        private func mergeSort(_ start: Int, _ end: Int, _ nums: inout [Int], _ helper: inout [Int]) -> Int {
            if start >= end {
                return 0
            }
            
            let middle = start + (end - start) / 2
            var count = mergeSort(start, middle, &nums, &helper) + mergeSort(middle + 1, end, &nums, &helper)
            var j = middle + 1
            
            for i in start...middle {
                while j <= end && Double(nums[i]) / 2.0 > Double(nums[j]) {
                    j += 1
                }
                count += j - (middle + 1)
            }
            
            mergeHelper(start, middle, end, &nums, &helper)
            
            return count
        }
        
        private func mergeHelper(_ start: Int, _ middle: Int, _ end: Int, _ nums: inout [Int], _ helper: inout [Int]) {
            for i in start...end {
                helper[i] = nums[i]
            }
            
            var n1 = start
            var n2 = middle + 1
            var i = start
            
            while n1 <= middle || n2 <= end {
                if n1 > middle || (n2 <= end && helper[n1] >= helper[n2]) {
                    nums[i] = helper[n2]
                    i += 1
                    n2 += 1
                } else {
                    nums[i] = helper[n1]
                    i += 1
                    n1 += 1
                }
            }
        }
    }
    

Log in to reply
 

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