正经用python如果过这题

前言

思路就是归并排序的时候计算逆序数量，但是python代码却总是超时。
查看了目前牛客网通过的代码基本上是，emmmm，一言难尽。

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        return 24903408 if data[0]==26819 else 493330277 if data[0]==627126 else 988418660 if data[0]==74073 else 2519
        # write code here

这比打表还更过分吧。

代码优化

基本能改的不多。

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        self.pair_num = 0
        self.data = data
        self.merge(0, len(self.data))
        return self.pair_num

    def merge(self, start, end):
        if start >= end - 1: return 
        mid = (start + end) // 2
        self.merge(start, mid)
        self.merge(mid, end)
        i,j = start,mid
        arr = [0]*(end-start)
        arr_index= 0
        while i < mid and j < end:
            if self.data[i] < self.data[j]:
                # arr.append(data[i])
                arr[arr_index] = self.data[i]
                i += 1
            else:
                self.pair_num += mid - i 
                if self.pair_num >= 1000000007:
                    self.pair_num -= 1000000007
                # arr.append(data[j])
                arr[arr_index] = self.data[j]
                j += 1
            arr_index += 1
        if i < mid:
            # arr.extend(data[i:mid])
            for x in range(i,mid):
                arr[arr_index] = self.data[x]
                arr_index += 1

        if j < end:
            # arr.extend(data[j:end])
            for x in range(j,end):
                arr[arr_index] = self.data[x]
                arr_index += 1
        self.data[start:end] = arr   

然鹅

基本是稳定在3秒上下。
多次实测还是偶尔可能出现超时。（玄学