剑指offer：数组中的逆序对-创新互联
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5示例1
输入 1,2,3,4,5,6,7,0
输出 7
# -*- coding: utf-8 -*-
# @Time : 2019-07-12 11:39
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : inversePairs.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
"""
要计算数组中的逆序对的对数，那么最直观的做法就是遍历整个数组，将当前元素和后续的所有元素进行
比较，然后累计有多少逆序对。
另一种解法就是基于归并排序的解法。
上述的解法的大缺陷在于每个数字都要跟后续的所有数字进行比较，导致时间复杂度为O(n^2)。
如果可以避免这么多次比较，就可以提高效率。
效仿归并排序，我们先将一个数组不断对半分裂，先得到多个长度为1的数组，然后每两个相邻数组进行比较
然后归并。
**之所以要进行归并(将这两个相邻数组合并后排序)是因为如果不排序的话，在下一轮的比较的时候会出现
重复计数的情况**
由于进行了排序，在下一轮归并的时候只需要将两个数组的大值进行比较，如果左边的数组的大值大于
右边数组的大值，那么说明右边整个数组都可以跟左边数组的大值组成逆序对，因此跳过左边数组大
值和右边剩余元素的比较。
这种解法其实就是**降序的归并排序**。
"""
def InversePairs(self, data):
def split(start, end):
# 先将整个数组对半分裂成若干个长度为1的数组
if start < end: # start < end，说明长度大于1，继续分裂
mid = (start + end) >> 1
split(start, mid)
split(mid + 1, end)
# 分裂完成后，对两个相邻数组进行归并
# 两个数组的下标分别为[start, mid], [mid + 1, end]
merge(start, mid, end)
def merge(start, mid, end):
# 由于我们这里的count是InversePairs()里的局部变量，
# 所以用nonlocal关键字而非global
nonlocal count
# 由于是进行降序归并，因此从两个数组的末尾开始归并
p1 = mid
p2 = end
while p1 >= start and p2 > mid:
# 如果左边大于右边，说明组成了一个逆序对，
# 计数器count增加数值为右边数组的剩余元素个数
if data[p1] > data[p2]:
# count += end - p2 + 1
count += p2 - mid
# data_copy用于存储归并后的结果
data_copy.append(data[p1])
p1 -= 1
else:
data_copy.append(data[p2])
p2 -= 1
# 将左右数组剩余的元素加入data_copy中，由于是有其中一个数组完全为空了，所以事实上
# 只将其中一个数组的元素加入data_copy中，而由于我们是利用递归实现的，这个数组也早
# 已有序，因此归并后的结果data_copy是有序的
for p in range(p1, start - 1, -1):
data_copy.append(data[p])
for p in range(p2, mid, -1):
data_copy.append(data[p])
# 将归并结果赋值到原数组中，注意这里赋值的顺序，我们要保证从小到大。
while data_copy:
data[start] = data_copy.pop(-1)
start += 1
if not data:
return 0
count = 0 # 用于统计逆序对的对数
data_copy = [] # 辅助数组，用于存储两个相邻数组归并的临时结果
split(0, len(data) - 1)
return count % 1000000007
def main():
solution = Solution()
data = [364, 637, 341, 406, 747, 995, 234, 971, 571, 219, 993, 407, 416,
366, 315, 301, 601, 650, 418, 355, 460, 505, 360, 965, 516, 648,
727, 667, 465, 849, 455, 181, 486, 149, 588, 233, 144, 174, 557, 67,
746, 550, 474, 162, 268, 142, 463, 221, 882, 576, 604, 739, 288,
569, 256, 936, 275, 401, 497, 82, 935, 983, 583, 523, 697, 478, 147,
795, 380, 973, 958, 115, 773, 870, 259, 655, 446, 863, 735, 784, 3,
671, 433, 630, 425, 930, 64, 266, 235, 187, 284, 665, 874, 80, 45,
848, 38, 811, 267, 575]
# data = [1,2,3,4,5,6,7,0]
print(solution.InversePairs(data))
if __name__ == '__main__':
main()另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
文章标题：剑指offer：数组中的逆序对-创新互联
标题路径：http://shouzuofang.com/article/csjidi.html