Python程序：查找反转反转

假设我们得到一个数字列表nums。我们必须找到满足a < b < c < d且nums[a] < nums[b]以及nums[c] > nums[d]的四元组(a, b, c, 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 := 新列表

  • 将nums的最后一项插入sorted_ds

  • 对列表sorted_ds排序

  • ds_smaller_than_c := [0] * n

  • 对于c从n − 2到−1递减，执行：

    • ds_smaller_than_c[c] := 返回sorted_ds中nums[c] − 1可以插入并保持排序顺序的最右位置

    • 将nums[c]插入sorted_ds的末尾

    • 对列表sorted_ds排序

  • quadruplet_count := 0

  • sorted_as := 新列表

  • 将nums的第一个数字插入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

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

    • 对列表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

更新于：2020-12-15

浏览量：114

开启你的职业生涯

完成课程获得认证

开始学习
广告