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

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• m :=10^9 + 7

• 숫자의 크기가 4보다 작으면

  • 0 반환

• n :=숫자 크기

• sorted_ds :=새 목록

• sorted_ds에 숫자의 마지막 항목 삽입

• 목록 정렬 sorted_ds

• ds_smaller_than_c :=[0] * n

• 범위 n − 2 ~ −1의 c에 대해 1 감소, do

  • ds_smaller_than_c[c] :=sorted_ds에서 가장 오른쪽 위치를 반환합니다. 여기서 nums[c] - 1을 삽입하고 정렬된 순서를 유지할 수 있습니다.

  • sorted_ds의 끝에 nums[c] 삽입

  • 목록 정렬 sorted_ds

• quadruplet_count :=0

• sorted_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 모드 m

  • sorted_as

    끝에 nums[b] 삽입

  • sorted_as

    목록 정렬

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

  • quadruplet_count :=quadruplet_count 모드 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