โปรแกรมค้นหา Inverted Inversions ใน Python

ดังนั้น หากอินพุตเป็น 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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=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 ลดลง 1 ทำ

  • ds_smaller_than_c[c] :=ส่งคืนตำแหน่งขวาสุดใน sorted_ds โดยที่nums[c] − 1 สามารถแทรกและเรียงลำดับการเรียงลำดับได้

  • ใส่ nums[c] ต่อท้าย sorted_ds

  • เรียงลำดับรายการ sorted_ds

• quadruple_count :=0

• sorted_as :=รายการใหม่

• ใส่ตัวเลขตัวแรกใน sorted_as

• เรียงลำดับรายการ sorted_as

• as_smaller_than_b_sum :=0

• สำหรับ b ในช่วง 1 ถึง n − 2 ทำ

  • 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 ม.

  • ใส่ 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

• ส่งคืน quadruple_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