पायथन में उल्टे व्युत्क्रम खोजने का कार्यक्रम

मान लीजिए कि हमें संख्याओं की एक सूची प्रदान की गई है। हमें मौजूदा चौपाइयों (ए, बी, सी, डी) की संख्या का पता लगाना है जैसे कि ए <बी <सी <डी और अंक [ए] <संख्या [बी] और अंक [सी]> अंक [डी]।

सरणी संख्या पूर्णांकों का क्रमपरिवर्तन है 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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मी :=10^9 + 7

• यदि अंकों का आकार <4 है, तो

  • वापसी 0

• n :=अंकों का आकार

• 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 को डाला जा सकता है और क्रमबद्ध क्रम को बनाए रखा जा सकता है

  • Sorted_ds के अंत में nums[c] डालें

  • सूची को क्रमबद्ध करें क्रमबद्ध करें

• चौगुनी_गिनती :=0

• Sorted_as :=एक नई सूची

• Sorted_as में अंकों की पहली संख्या डालें

• क्रमबद्ध_के रूप में सूची को क्रमबद्ध करें

• as_smaller_than_b_sum :=0

• b के लिए 1 से n - 2 की सीमा में, करें

  • as_smaller_than_b_sum :=as_smaller_than_b_sum + सबसे दाहिनी ओर इनसोर्ट की गई स्थिति जहां nums[b] – 1 को डाला जा सकता है और क्रमबद्ध क्रम को बनाए रखा जा सकता है

  • क्रमबद्ध_के रूप में सूची को क्रमबद्ध करें

  • as_smaller_than_b_sum :=as_smaller_than_b_sum mod m

  • सॉर्ट किए गए_as के अंत में nums[b] डालें

  • क्रमबद्ध_के रूप में सूची को क्रमबद्ध करें

  • चौगुनी_गिनती :=quadrulet_count + as_smaller_than_b_sum *ds_smaller_than_c[b + 1]

  • quadruple_count :=quadrulet_count mod m

• क्वाड्रुपलेट_काउंट लौटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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