在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_sum mod m

• 在sorted_as的末尾插入nums [b]

• 对列表进行排序sorted_as

• quadruplet_count：= quadruplet_count + as_smaller_than_b_sum * ds_smaller_than_c [b + 1]

• quadruplet_count：= quadruplet_count mod m

• 返回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