在Python中查找反演的程序
假设我们已经得到了一个数字列表。我们必须找到现有四元组(a,b,c,d)的数量，以使a<b<c<d和nums[a]<nums[b]和nums[c]>nums[d]。
数组nums是整数1...N的排列
因此，如果输入类似于nums=[3、4、7、6、5]，则输出将为5。
从给定的输入，我们有这些反转的反转-
3、4、7、6
3、4、6、5
3、4、7、5
3、7、6、5
4、7、6、5
为了解决这个问题，我们将遵循以下步骤-
m：=10^9+7
如果nums<4
返回0
n：=nums的大小
sorted_ds：=一个新列表
在sorted_ds中插入nums的最后一项
对列表进行排序sorted_ds
ds_smaller_than_c：=[0]*n
对于范围为n−2至-1的c，减1，
ds_smaller_than_c[c]：=返回sorted_ds中最右边的位置，可以插入nums[c]-1并保持排序顺序
在sorted_ds的末尾插入nums[c]
对列表进行排序sorted_ds
quadruplet_count：=0
sorted_as：=一个新列表
在sorted_as中插入第一个数字
对列表进行排序sorted_as
as_smaller_than_b_sum：=0
对于b在1到n−2的范围内，执行
as_smaller_than_b_sum：=as_smaller_than_b_sum+sorted_as中最右边的位置，可以插入nums[b]–1并保持排序顺序
对列表进行排序sorted_as
as_smaller_than_b_sum：=as_smaller_than_b_summodm
在sorted_as的末尾插入nums[b]
对列表进行排序sorted_as
quadruplet_count：=quadruplet_count+as_smaller_than_b_sum*ds_smaller_than_c[b+1]
quadruplet_count：=quadruplet_countmodm
返回quadruplet_count
让我们看下面的实现以更好地理解-
示例
import bisect
MOD = 10 ** 9 + 7
class Solution:
def solve(self, nums):
if len(nums) < 4:
return 0
n = len(nums)
sorted_ds = list([nums[−1]])
sorted_ds.sort()
ds_smaller_than_c = [0] * n
for c in range(n − 2, −1, −1):
ds_smaller_than_c[c] = bisect.bisect_right(sorted_ds, nums[c] − 1)
sorted_ds.append(nums[c])
sorted_ds.sort()
quadruplet_count = 0
sorted_as = list([nums[0]])
sorted_as.sort()
as_smaller_than_b_sum = 0
for b in range(1, n − 2):
as_smaller_than_b_sum += bisect.bisect_right(sorted_as, nums[b] − 1)
sorted_as.sort()
as_smaller_than_b_sum %= MOD
sorted_as.append(nums[b])
sorted_as.sort()
quadruplet_count += as_smaller_than_b_sum * ds_smaller_than_c[b + 1]
quadruplet_count %= MOD
return quadruplet_count
ob = Solution()
print(ob.solve([3, 4, 7, 6, 5]))输入值
[3, 4, 7, 6, 5]输出结果
5