Pythonで反転反転を見つけるプログラム

配列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

• n − 2〜-1の範囲のcの場合、1ずつ減少します。

  • ds_smaller_than_c [c]：=sorted_dsの右端の位置を返します。nums[c]− 1を挿入して、並べ替えた順序を維持できます

  • sort_dsの最後にnums[c]を挿入します

  • リストを並べ替えますsorted_ds

• quadruplet_count：=0

• sort_as：=新しいリスト

• 数値の最初の数をsorted_as

  に挿入します

• リストを並べ替えますsorted_as

• as_smaller_than_b_sum：=0

• 1からn− 2の範囲のbの場合、実行

  • as_smaller_than_b_sum：=as_smaller_than_b_sum+右端の位置insorted_asここでnums[b]– 1を挿入し、ソートされた順序を維持できます

  • リストを並べ替えますsorted_as

  • as_smaller_than_b_sum：=as_smaller_than_b_sum mod m

  • sort_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