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

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告