在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围： 对于
对于
数组中所有数字的值满足 
要求：空间复杂度 )
，时间复杂度 )
[编程题]数组中的逆序对
class Solution: def InversePairs(self, data): self.count = 0 res = self.mergersort(data) return self.count def mergersort(self,data): n = len(data) if n<=1: return data mid = n//2 left = self.mergersort(data[:mid]) right = self.mergersort(data[mid:]) return self.merge(left,right) def merge(self,left,right): data = [] l = 0 r = 0 while l < len(left) and r<len(right): if left[l]<right[r]: data.append(left[l]) l+=1 else: data.append(right[r]) r+=1 self.count += len(left)-l if l == len(left): data.extend(right[r:]) else: data.extend(left[l:]) self.count = self.count%1000000007 return data
发表于 2022-04-03 16:17:08
回复(0)
通过全部测试用例，超过百分之90用户。现在测试时间不够的问题应该已经修复了
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.sol = 0 def InversePairs(self, data): self.merge_sort(data) return self.sol % 1000000007 def merge_sort(self,data): if len(data)==1: return data mid = len(data)//2 return self.merge(self.merge_sort(data[:mid]), self.merge_sort(data[mid:])) def merge(self, left, right): output = [] while len(left)!=0 and len(right)!=0: if left[0]>right[0]: output.append(right.pop(0)) self.sol += (len(left)) else: output.append(left.pop(0)) output += left output += right return output
发表于 2021-05-25 19:26:53
回复(0)
# -*- coding:utf-8 -*- class Solution: def InversePairs(self, data): # 分治 + 排序, 时间复杂度 O(NlogN) # 将数组对半分成A, B两部分，那么总的逆序对数就等于A、B各自内部的逆序对数加上A、B之间的逆序对数 # A、B之间的逆序对数可以这么求：A、B内部各自排序，然后用两个指针将A、B各扫一遍即可，时间复杂度O(NlogN + N) # A、B各自内部的逆序对数用递归即可 def calInvPairs(data, a, b): # 计算data[a:b]的逆序对数 # 递归结束条件 if b-a<=1: return 0 elif b-a==2: return int(data[a]>data[b-1]) # 返回1或者0 # 计算A、B区间各自的逆序数 m = (a+b)//2 countA = calInvPairs(data, a, m) countB = calInvPairs(data, m, b) # 计算 data[a:m] 与 data[m:b] 之间的逆序数 # 注意一定要先算完上面两个，再算这个。这样就可以直接在原位排序，省内存。 # 呃呃呃，list没有原位排序的内置方法，这里就多耗点内存吧 >_< dataA = sorted(data[a:m]) dataB = sorted(data[m:b]) countAB = 0 iB = 0 lenB = len(dataB) for val in dataA: # 统计dataB中有多少个数是小于val的 # 这里用到了"每次循环，val是单调递增的"这一性质 while (iB<lenB) and (dataB[iB]<val): iB+=1 # 运行到这里，有两种可能： # 1. dataB[iB-1] < val 且 iB==lenB # 2. dataB[iB-1] < val < dataB[iB] countAB += iB countAB %= 1000000007 return (countA + countB + countAB) % 1000000007 return calInvPairs(data, 0, len(data))
发表于 2021-04-29 00:02:04
回复(0)
class Solution: def InversePairs(self, nums): # write code here n = len(nums) tmp = [0] * n self.cnt = 0 self.merge_sort(nums, 0, n-1, tmp) return self.cnt def merge_sort(self, nums, low, high, tmp): if low >= high: return 0 mid = low + (high - low) // 2 self.merge_sort(nums, low, mid, tmp) self.merge_sort(nums, mid+1, high, tmp) i, j, k = low, mid+1, low while i <= mid and j <= high: if nums[i] <= nums[j]: tmp[k] = nums[i] i += 1 else: tmp[k] = nums[j] j += 1 self.cnt = (self.cnt + (mid-i+1)) % 1000000007 k += 1 while i <= mid: tmp[k] = nums[i] i += 1 k += 1 while j <= high: tmp[k] = nums[j] j += 1 k += 1 nums[low:high+1] = tmp[low:high+1] return
发表于 2021-04-17 13:46:18
回复(0)
# -*- coding:utf-8 -*- class Solution: #用来定义一个count，就可以不断的在原来基础上叠加了 def __init__(self): self.count = 0 def InversePairs(self, data): # write code here #这个是用来合的函数，返回res，只是在合的过程中可以用来计算count def merge(s1, s2): res = [] i = j = 0 n = len(s1) m = len(s2) while i < n and j < m: if s1[i] > s2[j]: self.count += n - i res.append(s2[j]) j += 1 else: res.append(s1[i]) i += 1 res += s1[i:] if i < n else s2[j:] return res #这个是用来分的函数，就是一直分分分，直到列表中只剩下1个 def merge_sort(li): if len(li) == 1: return li if len(li)<1: return [] mid = len(li)//2 lt = merge_sort(li[:mid]) rt = merge_sort(li[mid:]) return merge(lt, rt) #就是用来merge后看看count多少，最后返回一下就行了 if len(data) < 2: return 0 merge_sort(data) return self.count%1000000007分治法，归并排序，好处是比较一下就可以输出好多不重复的答案
发表于 2020-11-29 10:19:46
回复(1)
# 不用递归的归并排序，可以通过 # -*- coding:utf-8 -*- res = 0 class Solution: def InversePairs(self, data): # write code here def double_sort(left, right): global res l, r, got = 0, 0, [] while l < len(left) and r < len(right): if left[l] < right[r]: got.append(left[l]) l += 1 else: got.append(right[r]) res += len(left)-l # 较小的数移到所有比它大的数的前面 r += 1 got += left[l :] got += right[r :] return got if not data: return 0 global res res = 0 d = 2; while d < len(data)*2: for i in range(0, len(data), d): data[i:min(i+d,len(data))] = double_sort(data[i:i+d/2], data[i+d/2:min(i+d,len(data))]) d *= 2 data = double_sort(data[: d/2], data[d/2 :]) # 最后的合并 return res%1000000007
编辑于 2020-09-01 16:38:15
回复(0)
没有想到这个题目还可以用分治排序算法来做，不知道是不是有其他排序算法也可以用来求解逆序对。
我一开始写了个暴力求解的，时间复杂度太高只通过了50%，即依次求每个数后面小于它的数的总数，最后相加。
分治算法求解则是将一个数组分成相等的两份，分别求解两个子数组中的逆序对数目并排序，然后再求两个排好序后的数组构成多少的逆序对——这里比较关键，如果前面数组的最后一个大于后面数组的最后一个，则前面数组的最后一个和后面数组的所有数构成逆序对。
# -*- coding:utf-8 -*-
class Solution:
def InversePairsCore(self, data,copy1,start,end):
if start == end:
copy1[start] = data[start]
return 0
mid = (start+end)>>1
left = self.InversePairsCore(data,copy1,start,mid)
right = self.InversePairsCore(data,copy1,mid+1,end)
count = 0
end1 = mid
end2 = end
copy_index = end
while end1>=start and end2>mid:
if data[end1]>data[end2]:
copy1[copy_index] = data[end1]
end1 -= 1
copy_index -= 1
count += (end2-mid)
else:
copy1[copy_index] = data[end2]
end2 -= 1
copy_index -= 1
while end1>=start:
copy1[copy_index] = data[end1]
end1 -= 1
copy_index -= 1
while end2>mid:
copy1[copy_index] = data[end2]
end2 -= 1
copy_index -= 1
data[start:end+1] = copy1[start:end+1]
return (left+right+count)%1000000007
def InversePairs(self, data):
# write code here
# 依次求每个数后面小于它的数的总数，最后相加
# 暴力求解法（时间复杂度过高）
'''
l = len(data)
cnts = [0 for i in range(l)]
for i in range(l-1)[::-1]:
for j in range(i+1, l):
if data[j]<data[i]:
cnts[i] += 1
return sum(cnts)%1000000007
'''
# 归并排序算法求解
import copy
data_copy = copy.deepcopy(data)
return self.InversePairsCore(data,data_copy,0,len(data)-1)
编辑于 2020-08-04 14:36:22
回复(0)
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.totals = 0 def InversePairs(self, data): # write code here self.merge(data) return self.totals%1000000007 def mergeSort(self, num1, num2): result = [] i, j = 0, 0 while(i<len(num1) and j<len(num2)): if num1[i]<=num2[j]: ###只有在这个的时候才计算逆序对，这时是计算num[i]所对应的逆序对 self.totals += j result.append(num1[i]) i += 1 else: result.append(num2[j]) j += 1 while(i<len(num1)): self.totals += j result.append(num1[i]) i += 1 while(j<len(num2)): result.append(num2[j]) j += 1 return result def merge(self, numbers): if len(numbers)<2: return numbers mid = int(len(numbers)/2) return self.mergeSort(self.merge(numbers[:mid]), self.merge(numbers[mid:]))python的归并排序
发表于 2020-06-16 16:08:06
回复(0)
class Solution: def __init__(self): self.count = 0 def InversePairs(self, data): if len(data)<=0: return 0 self.mergeSort(data) return self.count % 1000000007 def mergeSort(self,data): if len(data) < 2: return data midIndex = len(data)>>1 leftlist = self.mergeSort(data[:midIndex]) rightlist = self.mergeSort(data[midIndex:]) return self.merge(leftlist,rightlist) def merge(self,leftlist,rightlist): resultlist = [] #辅助数组记录排序后的结果 i,j =len(leftlist)-1,len(rightlist)-1 (3337)#注意这里ij初始化为最后一个元素，因为是从后往前比较，便于计算count while i>=0 and j >= 0: if leftlist[i] > rightlist[j]: self.count += (j+1)#就是比归并排序多了这一步 resultlist.append(leftlist[i]) (3338)#按从大到小排 i -= 1 else: resultlist.append(rightlist[j]) j -= 1 #接上剩余的元素 resultlist = resultlist[::-1] (3339)#注意做个翻转 resultlist = leftlist[:i+1] + resultlist resultlist = rightlist[:j+1] + resultlist return resultlist Solution().InversePairs([7,5,6,4])
发表于 2020-03-22 22:02:55
回复(0)
拿我的代码和交上去AC的代码都比对了，测试输出都一样，但是还是75测试点通过，显示超时让检查循环和算法复杂度，而且发现AC的python代码有的是把等于的也算逆序对了？但是>和>=对于我的代码交上去都一样是超时，不知道为啥，至于边界不必纠结，求大佬超时问题看看~class Solution: def __init__(self): self.cnt = 0 def InversePairs(self, data): # write code here self.FindPairs(data, 0, len(data) - 1) return self.cnt % 1000000007 def FindPairs(self, data, start, end): if start < end: mid = (start + end) // 2 self.FindPairs(data, start, mid) self.FindPairs(data, mid + 1, end) self.MergePairs(data, start, mid, end) def MergePairs(self, data, start, mid, end): mergecnt = 0 i = start j = mid + 1 k = 0 temp = [] while i <= mid and j <= end: if data[i] > data[j]: temp.append(data[j]) j += 1 mergecnt += (mid - i + 1) else: temp.append(data[i]) i += 1 if i <= mid: temp.extend(data[i:mid+1]) if j <= end: temp.extend(data[j:end+1]) data[start:end + 1] = temp[0: end - start + 1] self.cnt += mergecnt
编辑于 2020-02-08 00:10:30
回复(0)
# -*- coding:utf-8 -*-
# 解题思路：归并排序实现逆序对统计
class Solution:
def InversePairs(self, data):
# write code here
res = {'k': 0}
def merge_sort(ls):
if len(ls) == 1:
return ls
mid = len(ls) // 2
left = merge_sort(ls[0: mid])
right = merge_sort(ls[mid:])
return merge_list(left, right)
def merge_list(ls1, ls2):
i = 0
j = 0
rs = []
while i < len(ls1)&nbs***bsp;j < len(ls2):
if i == len(ls1):
while j < len(ls2):
rs.append(ls2[j])
j += 1
i += 1
break
if j == len(ls2):
while i < len(ls1):
rs.append(ls1[i])
i += 1
j += 1
break
if ls1[i] > ls2[j]:
rs.append(ls2[j])
# 如果左数组顶部数字比右数组顶部数字大，那么左数组i之后的都比右数组顶部数字
# res += len(ls1) - i (注意：因为python2中没有nolocal关键字，所以用一个字典替代)
res['k'] += len(ls1) - i
j += 1
else:
rs.append(ls1[i])
i += 1
return rs
merge_sort(data)
return res['k'] % 1000000007
发表于 2020-01-18 20:11:37
回复(0)
链接：https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5?f=discussion
来源：牛客网
来源：牛客网
思路分析：
看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)这个数字比较，因此这个算法的时间复杂度为O(n^2)。
我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不拿ta和后面的每一个数字作比较，否则时间复杂度就是O(n^2)，因此我们可以考虑先比较两个相邻的数字。
(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；
在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图（c）所示， 以免在以后的统计过程中再重复统计。
接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。
过程：先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序。参考代码如下：
class Solution: def __init__(self): self.count = 0 def InversePairs(self, data): # write code here self.MergeSort(data) return self.count%1000000007 def MergeSort(self,lists): #global count if len(lists) <= 1: return lists num = int( len(lists)/2 ) left = self.MergeSort(lists[:num]) right = self.MergeSort(lists[num:]) r, l=0, 0 result=[] while l<len(left) and r<len(right): if left[l] < right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 self.count += len(left)-l if r>=len(right):#某一遍排序完了，把另一边的补过来 return result+ left[l:] else: return result + right[r:]
发表于 2019-12-30 17:29:21
回复(1)
用归并排序的算法,在每次归并的时候记录次数
# -*- coding:utf-8 -*- class Solution: def InversePairs(self, data): def gbsort(data,l,r): if l>=r: return 0 mid=l+(r-l)//2 lc=gbsort(data,l,mid) rc=gbsort(data,mid+1,r) ac=merge(data,l,mid,r) return lc+rc+ac def merge(data,l,mid,r): i=l j=mid+1 t=[] c=0 while i<=mid and j<=r: if data[i]<=data[j]: t.append(data[i]) i+=1 else: t.append(data[j]) c+=(mid+1-i) j+=1 while i<=mid: t.append(data[i]) i+=1 while j<=r: t.append(data[j]) j+=1 data[l:r+1]=t return c return gbsort(data,0,len(data)-1)%1000000007
发表于 2019-11-06 18:38:11
回复(0)
class Solution: def __init__(self): self.cnt = 0 # 统计逆序对数 def digui(self, data): if len(data) <= 1: # 已分到最后，无需排序，直接返回 return data mid = len(data) // 2 # 平分点 left = self.digui(data[:mid]) # 升序的左半子数组 right = self.digui(data[mid:]) # 升序的右半子数组 res = [] # 辅助数组，保存归并升序后的数组 k, m = 0, 0 # 记录遍历的左右半子数组的索引 # 遍历左右半子数组，统计其中的逆序对 while k < len(left) and m < len(right): if left[k] < right[m]: res.append(left[k]) k += 1 continue else: res.append(right[m]) m += 1 self.cnt += len(left) - k if k == len(left): # 如果是左半子数组先遍历完，则把剩下的右半子数组加入res后面（此时右半子数组中已全是大于左半子数组所有数的数） res += right[m:] if m == len(right): res += left[k:] return res def InversePairs(self, data): # write code here self.digui(data) return self.cnt % 1000000007运行3138ms，超过了2秒的时间限制，不过还是通过了😳
发表于 2019-08-15 17:14:51
回复(0)
Python归并排序解法 AC
class Solution:
def __init__(self):
self.count = 0
def mergeSort(self, data):
if len(data) < 2: return data
mid = len(data)//2
left = self.mergeSort(data[:mid])
right = self.mergeSort(data[mid:])
i, j = 0, 0
res = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
self.count += (len(left)-i)
return res + left[i:] + right[j:]
def InversePairs(self, data):
# write code here
if len(data) < 2: return 0
self.mergeSort(data)
return self.count % 1000000007
编辑于 2019-07-31 10:02:40
回复(0)
merge sort 在合并过程中计算逆序数。
合并前后a b两个小段时，后面小段b里面的小的数字插入前面的小段a时，插入位置后的数字个数就是逆序数（因为每一个小段都是排好序的，即a是排序的）
代码中注释的位置是本题的关键
class Solution: def InversePairs(self, data): l = 0 h = len(data)-1 _, num = self.mergesort(data,l,h) return num def mergesort(self,data, l,h): if l==h: return [data[l]],0 mid = (h+l)//2 ordered_l, num_l= self.mergesort(data,l,mid) ordered_h, num_h = self.mergesort(data,mid+1,h) ordered_all, num=self.merge_reverse_count(ordered_l, ordered_h) cnt = (num_l+num_h+num)%1000000007 return ordered_all, cnt def merge_reverse_count(self,l, h): ll = len(l) lh = len(h) i = 0 j = 0 arr = [] tmp_cnt = 0 while i<ll and j<lh: if l[i]<=h[j]: arr.append(l[i]) i+=1 else: # 逆序！！！ arr.append(h[j]) tmp_cnt+=(ll-i) j+=1 if i==ll: arr+=h[j:] if j==lh: arr+=l[i:] return arr, tmp_cnt%1000000007
编辑于 2019-07-25 12:02:42
回复(0)
归并排序，在归并的过程中count
# -*- coding:utf-8 -*- class Solution: def InversePairs(self, data): # write code here self.arr, self.count = data, 0 self.merge_sort(0, len(data)-1) return self.count % 1000000007 def merge_sort(self, l, r): if l >= r: return m = int((l+r+1)/2) self.merge_sort(l, m-1) self.merge_sort(m, r) i, j, merge = l, m, [] while i < m and j <= r: if self.arr[i] < self.arr[j]: merge.append(self.arr[i]) i += 1 else: merge.append(self.arr[j]) j += 1 self.count += m - i for x in range(j,r+1): merge.append(self.arr[x]) for x in range(i,m): merge.append(self.arr[x]) for i in range(l, r+1): self.arr[i] = merge[i-l]
发表于 2019-05-25 17:10:12
回复(0)
# Python Solution: # 代码写的比较丑陋，怕内存超限，没有使用递归，后面会在雕琢一下，大家将就看先; class Solution: def InversePairs(self, data): l = len(data) l1 = 1 count = 0 while(l1<=l): # 若l的长度不能表示为2*n，以2为步长，取不到全长时的情况 l1 *= 2 # 2，4，8，16为一个分组单元，直到单元的长度长于l,代表上一次最多有两个分组单元，此时应该合并为一个序列 j = 0 while (j < l): # j是分组单元起始点 left = j # 当 left=0 时，right=1,分别指向最左侧元素位置和最右侧元素右边的位置 right = j + l1//2 if (j + l1//2 )< l else l # right有可能指向left一侧的元素 tmp = [] if (right==l): # 代表只有左侧元素 break li = left ri = right rb = min(right+l1//2,l) while(li<right and ri<rb): if(data[li]<data[ri]): tmp.append(data[li]) li += 1 else: res = l1//2-(li-left) count += res tmp.append(data[ri]) ri += 1 while(li<right): tmp.append(data[li]) li += 1 while(ri<rb): tmp.append(data[ri]) ri += 1 k = 0 for i in range(left,rb): data[i] = tmp[k] k += 1 j += l1 left = 0 right = j + l1 // 2 if (j + l1 // 2) < l else l # right有可能指向left一侧的元素 tmp = [] # if (right == l): # 该情况被舍去，因若只有左侧元素，则在上一次分组已经分完 # break li = left ri = right rb = min(right + l1//2, l) while (li < right and ri < rb): if (data[li] < data[ri]): tmp.append(data[li]) li += 1 else: res = l1//2 - (li - left) count += res tmp.append(data[ri]) ri += 1 while (li < right): tmp.append(data[li]) li += 1 while (ri < rb): tmp.append(data[ri]) ri += 1 k = 0 for i in range(left, rb): data[i] = tmp[k] k += 1 return count%1000000007
发表于 2019-05-06 20:09:23
回复(0)
解题思路：每次找到数组中的最小值，最小值前面有几个数则对他而言就有几个逆序对。然后再删除这个最小值，重复相同的步骤，知道数组变成空值。这个求解过程为什么时间复杂度会这个高，非cs专业小白求助各位大神。代码如下，案例能通过。
class Solution:
def InversePairs(self, data):
count=0
while len(data)!=0:
min_data=min(data)
count+=data.index(min_data)
data.remove(min_data)
return count
发表于 2019-04-24 11:42:48
回复(0)
问题信息
难度：
43条回答
6195收藏
171592浏览
通过挑战的用户
查看代码-
2023-03-11 20:20:12 -
2022-12-06 16:25:33
-
2022-10-27 15:55:36
-
2022-10-16 14:27:16
-
2022-09-18 20:27:28
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
