Chương trình tìm các đảo ngược trong Python

Số mảng là một hoán vị của các số nguyên 1 ... N

Vì vậy, nếu đầu vào là nums =[3, 4, 7, 6, 5], thì đầu ra sẽ là 5.

Từ đầu vào đã cho, chúng ta có các phép đảo ngược này -

• 3, 4, 7, 6

• 3, 4, 6, 5

• 3, 4, 7, 5

• 3, 7, 6, 5

• 4, 7, 6, 5

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7

• nếu kích thước của nums <4, thì

  • trả về 0

• n:=kích thước của nums

• sorted_ds:=một danh sách mới

• Chèn mục cuối cùng trong số các số trong sorted_ds

• sắp xếp danh sách sorted_ds

• ds_smaller_than_c:=[0] * n

• đối với c trong phạm vi n - 2 đến −1, giảm 1, thực hiện

  • ds_smaller_than_c [c]:=trả lại vị trí ngoài cùng bên phải trong sorted_ds khi [c] - 1 có thể được chèn và có thể duy trì thứ tự đã sắp xếp

  • chèn nums [c] vào cuối sorted_ds

  • sắp xếp danh sách sorted_ds

• quadruplet_count:=0

• sorted_as:=một danh sách mới

• chèn số nums đầu tiên trong sorted_as

• sắp xếp danh sách sorted_as

• as_smaller_than_b_sum:=0

• đối với b trong phạm vi 1 đến n - 2, thực hiện

  • as_smaller_than_b_sum:=as_smaller_than_b_sum + vị trí ngoài cùng bên phải insorted_as nơi có thể chèn nums [b] - 1 và có thể duy trì thứ tự đã sắp xếp

  • sắp xếp danh sách sorted_as

  • as_smaller_than_b_sum:=as_smaller_than_b_sum mod m

  • chèn nums [b] vào cuối sorted_as

  • sắp xếp danh sách sorted_as

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

  • quadruplet_count:=quadruplet_count mod m

• trả về quadruplet_count

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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]))

Đầu vào

[3, 4, 7, 6, 5]

Đầu ra

5