Swift.数组中的逆序对

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字

import Foundation

class For36Solution {
    func inversePairs(_ nums: [Int]) -> Int {
        var n = nums
        return process(&n, 0, n.count - 1)
    }
    
    func process(_ nums: inout [Int],_ start: Int,_ end: Int) -> Int {
        
        if start >= end {
            return 0
        }
        
        var copy = Array(nums)
        let mid = (start + end) / 2
        let left = process(&nums, start, mid)
        let right = process(&nums, mid+1, end)
        
        var p = mid //前半段最后一个
        var q = end //后半段最后一个
        var index = end //辅助数组从最后一位开始
        var count = 0
        
        while p >= start && q >= mid+1 {
            if nums[p] > nums[q] {
                copy[index] = nums[p]
                count += q - mid
                index -= 1
                p -= 1
            }else {
                copy[index] = nums[q]
                index -= 1
                q -= 1
            }
        }
        
        while p >= start {
            copy[index] = nums[p]
            index -= 1
            p -= 1
        }
        
        while q >= mid + 1 {
            copy[index] = nums[q]
            index -= 1
            q -= 1
        }
        
        index = start
        while index <= end {
            nums[index] = copy[index]
            index += 1
        }
        
        
        return left + right + count
    }
}

算法思想：很容易想到的方法就是遍历每一个元素，让其与后面的元素对比，如果大于则count++，但是这样的时间复杂度是O(n2)，因此，我们可以用归并排序思路。

github地址：https://github.com/cubegao/LeetCode