基于冒泡
没想到冒泡也能过
基本思想
直接对数组进行冒泡排序,排序思想依然是**如果 i 定位的那个数比后面的大就换位**
这时,只要盯着一个数看(如第一个数,就会发现,它如果比后面的大就会被换到第一个小于它的位置
等 i 定位再次扫到它时它再与后面的比较,碰到比它小的,它就会被换到第二个比它小的位置
类推到底 就会记录整个数组后面有多少比它小
**记录数量**,比后面大也就是逆序对
类推到每个数 (但位置改变了 -->解释如下
j 位置被换到前面 **中间的数肯定比 i 位置大 同时也就比 j 位置的大**
那么 j 位置的数 是 i位置的 或 j位置的 都不影响逆序对的数量
(**扫到中间数的时候依然会记 它与j位置的数 为一对逆序对**
那么当冒泡完
也就记录完逆序对的数量
Python3 代码
class Solution(object):
def inversePairs(self, nums):
s = 0
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] > nums[j]:
nums[i],nums[j] = nums[j],nums[i]
s += 1
return s
基于归并
相比冒泡,归并的时间复杂度更低,但此题两种算法,运行时间相差不大,是数据的问题。
同样的题有 788-逆序对的数量 冒泡就会超时
基本思想
基本的归并分治思路 **重点是如何记录逆序对的数量**
数组二分划到底 合并时
l数组 记录的左边 r数组 记录的右边
于是当l中的数据插入 合并数组res 时
**记录res数组中已经插入了多少个r数组中的数**
Python3 代码
class Solution(object):
def inversePairs(self, nums):
s = 0
nums,s = self.gb(nums,s)
return s
def gb(self,line,s):
if len(line) <= 1:
return (line,s)
mid = len(line)//2
l,s = self.gb(line[:mid],s)
r,s = self.gb(line[mid:],s)
res = []
k = 0
for i in range(len(l)): # 定位 l数组 的数依次插入
for j in range(k,len(r)): # 插入 r数组 中的数直到比l大
if l[i] > r[j]:
res += [r[j]]
k += 1
else:
s += len(res)-i
res += [l[i]]
break
if k == len(r): # 如果 r数组 全部插入完 直接插入 l数组
s += len(res)-i
res += [l[i]]
for j in range(k,len(r)): # 如果 r数组 没插入完 补入
res += [r[j]]
return (res,s)