Swift solution - Merge Sort


  • 0
    class Solution {
        func countRangeSum(_ nums: [Int], _ lower: Int, _ upper: Int) -> Int {
            let count = nums.count
            var sums = [Int](repeatElement(0, count: count + 1) )
            
            for i in 0..<count {
                sums[i + 1] = sums[i] + nums[i]
            }
            
            return mergeSort(&sums, 0, count + 1, lower, upper)
        }
        
        private func mergeSort(_ sums: inout [Int], _ start: Int, _ end: Int, _ lower: Int, _ upper: Int) -> Int {
            if end - start <= 1 {
                return 0
            }
            
            let middle = start + (end - start) / 2
            var count = mergeSort(&sums, start, middle, lower, upper) + mergeSort(&sums, middle, end, lower, upper)
            var j = middle
            var k = middle
            var t = middle
            var cache = [Int](repeatElement(0, count: end - start))
            var r = 0
            
            for i in start..<middle {
                while k < end && sums[k] - sums[i] < lower {
                    k += 1
                }
                while j < end && sums[j] - sums[i] <= upper {
                    j += 1
                }
                while t < end && sums[t] < sums[i] {
                    cache[r] = sums[t]
                    r += 1
                    t += 1
                }
                cache[r] = sums[i]
                count += (j - k)
                r += 1
            }
            
            for i in 0...(t - start - 1) {
                sums[i + start] = cache[i]
            }
            
            return count
        }
    }
    

Log in to reply
 

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