python3 解法, 执行用时: 1644 ms, 内存消耗: 20.1 MB, 提交时间: 2022-11-30 23:44:10

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & (-x)
    
    def query(self, x):
        ret = 0
        while x > 0:
            ret += self.tree[x]
            x -= BIT.lowbit(x)
        return ret

    def update(self, x):
        while x <= self.n:
            self.tree[x] += 1
            x += BIT.lowbit(x)

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        # 离散化
        tmp = sorted(nums)
        for i in range(n):
            nums[i] = bisect.bisect_left(tmp, nums[i]) + 1
        # 树状数组统计逆序对
        bit = BIT(n)
        ans = 0
        for i in range(n - 1, -1, -1):
            ans += bit.query(nums[i] - 1)
            bit.update(nums[i])
        return ans

golang 解法, 执行用时: 128 ms, 内存消耗: 7.1 MB, 提交时间: 2022-11-30 23:43:49

func reversePairs(nums []int) int {
     n := len(nums)
     tmp := make([]int, n)
     copy(tmp, nums)
     sort.Ints(tmp)

     for i := 0; i < n; i++ {
         nums[i] = sort.SearchInts(tmp, nums[i]) + 1
     }

     bit := BIT{
         n: n,
         tree: make([]int, n + 1),
     }

     ans := 0
     for i := n - 1; i >= 0; i-- {
         ans += bit.query(nums[i] - 1)
         bit.update(nums[i])
     }
     return ans
}

type BIT struct {
    n int
    tree []int
}

func (b BIT) lowbit(x int) int { return x & (-x) }

func (b BIT) query(x int) int {
    ret := 0
    for x > 0 {
        ret += b.tree[x]
        x -= b.lowbit(x)
    }
    return ret
}

func (b BIT) update(x int) {
    for x <= b.n {
        b.tree[x]++
        x += b.lowbit(x)
    }
}

golang 解法, 执行用时: 128 ms, 内存消耗: 8 MB, 提交时间: 2022-11-30 23:43:29

func reversePairs(nums []int) int {
    return mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, start, end int) int {
    if start >= end {
        return 0
    }
    mid := start + (end - start)/2
    cnt := mergeSort(nums, start, mid) + mergeSort(nums, mid + 1, end)
    tmp := []int{}
    i, j := start, mid + 1
    for i <= mid && j <= end {
        if nums[i] <= nums[j] {
            tmp = append(tmp, nums[i])
            cnt += j - (mid + 1)
            i++
        } else {
            tmp = append(tmp, nums[j])
            j++
        }
    }
    for ; i <= mid; i++ {
        tmp = append(tmp, nums[i])
        cnt += end - (mid + 1) + 1
    }
    for ; j <= end; j++ {
        tmp = append(tmp, nums[j])
    }
    for i := start; i <= end; i++ {
        nums[i] = tmp[i - start]
    }
    return cnt
}

python3 解法, 执行用时: 1292 ms, 内存消耗: 20.5 MB, 提交时间: 2022-11-30 23:43:13

class Solution:
    def mergeSort(self, nums, tmp, l, r):
        if l >= r:
            return 0

        mid = (l + r) // 2
        inv_count = self.mergeSort(nums, tmp, l, mid) + self.mergeSort(nums, tmp, mid + 1, r)
        i, j, pos = l, mid + 1, l
        while i <= mid and j <= r:
            if nums[i] <= nums[j]:
                tmp[pos] = nums[i]
                i += 1
                inv_count += (j - (mid + 1))
            else:
                tmp[pos] = nums[j]
                j += 1
            pos += 1
        for k in range(i, mid + 1):
            tmp[pos] = nums[k]
            inv_count += (j - (mid + 1))
            pos += 1
        for k in range(j, r + 1):
            tmp[pos] = nums[k]
            pos += 1
        nums[l:r+1] = tmp[l:r+1]
        return inv_count

    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        tmp = [0] * n
        return self.mergeSort(nums, tmp, 0, n - 1)