在 Python 中找到反序倒置

假设我们有一个数字列表 nums。我们必须找到现有四元组（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
对于 c in range(n − 2, -1)，递减做
- ds_smaller_than_c[c] := 返回 sorted_ds 中 nums[c] – 1 可以插入并维护排序顺序的最右端位置
- 在 sorted_ds 的末尾插入 nums[c]
- 排序列表 sorted_ds
quadruplet_count := 0
sorted_as := 一个新列表
在 sorted_as 中插入 nums 的第一个数字
按排序顺序排序列表 sorted_as
as_smaller_than_b_sum := 0
对于 b in range(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]))