পাইথনে আরোহী ক্রমে উপাদান মুছে ফেলার পর একটি তালিকার সূচক পেতে প্রোগ্রাম

ধরুন আমাদের কাছে স্বতন্ত্র মানের একটি তালিকা আছে এবং আমরা প্রতিটি সংখ্যাকে অ-হ্রাস না হওয়া ক্রমে সরাতে চাই। তাদের মুছে ফেলার জন্য আমাদের সংখ্যার সূচকগুলি খুঁজে বের করতে হবে৷

সুতরাং, ইনপুট যদি nums =[4, 6, 2, 5, 3, 1] এর মত হয়, তাহলে আউটপুট হবে [5, 2, 3, 0, 1, 0] যেমন আমরা 1 মুছে ফেলব, তাই অ্যারে হল [ 4, 6, 2, 5, 3], তারপর 2 মুছে ফেলুন, অ্যারে হল [4, 6, 5, 3], তারপর 3 সরান আমরা [4, 6, 5] পাব, তারপর 4 সরান আমরা [6, 5] পাই , 5, [6] সরান এবং অবশেষে 6 সরান।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন my_sort() সংজ্ঞায়িত করুন। এর জন্য inds লাগবে
• যদি ইন্ডসের আকার <=1 হয়, তাহলে
  • ইন্ডস ফেরত দিন
• sorted_inds :=একটি নতুন তালিকা
• mid :=inds / 2 এর আকার
• বামে :=my_sort(inds[index 0 থেকে mid]), ডানে :=my_sort(inds[index mid থেকে end])
• i :=0, j :=0
• যখন i <বাম সাইজ এবং j <ডান সাইজ, do
  • যদি nums[left[i]]
  • sorted_inds-এর শেষে বাঁদিকে [i] সন্নিবেশ করুন
  • i :=i + 1
• অন্যথায়,
  • সর্টেড_ইন্ডের শেষে ডানদিকে [j] সন্নিবেশ করুন
  • বৃহত্তর[ডান[জে]] :=বড়[ডান[জে]] + বামের আকার - i
  • j :=j + 1

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class Solution:
   def solve(self, nums):
      return solve(nums)
def solve(nums):
   def my_sort(inds):
      if len(inds) <= 1:
         return inds
      sorted_inds = []
      mid = len(inds) // 2
      left, right = my_sort(inds[:mid]), my_sort(inds[mid:])
      i = j = 0
      while i < len(left) and j < len(right):
         if nums[left[i]] < nums[right[j]]:
            sorted_inds.append(left[i])
            i += 1
         else:
            sorted_inds.append(right[j])
            larger[right[j]] += len(left) - i
            j += 1
      sorted_inds.extend(left[i:])
      sorted_inds.extend(right[j:])
      return sorted_inds
   larger = [0] * len(nums)
   my_sort(range(len(nums)))
   num_larger_pairs = sorted(zip(nums, larger))
   return [e[1] for e in num_larger_pairs]
ob = Solution()
nums = [4, 6, 2, 5, 3, 1]
print(ob.solve(nums))

ইনপুট

[4, 6, 2, 5, 3, 1]

আউটপুট

[5, 2, 3, 0, 1, 0]