পাইথনে অ্যাসেন্ডিং অর্ডারে এলিমেন্ট ডিলিট করলে ইন্ডেক্স সিকোয়েন্স বের করার প্রোগ্রাম

একটি ডISTINCT ভ্যালুর লিস্ট nums দেওয়া আছে। সংখ্যাগুলো নন-ডিক্রিজিং অর্ডারে ডিলিট করা হবে। ডিলিশনের সময় প্রতিটি সংখ্যার তখনকার ইন্ডেক্স কত ছিল, সেটি আউটপুট করতে হবে।

উদাহরণস্বরূপ, nums = [4, 6, 2, 5, 3, 1] হলে আউটপুট [5, 2, 3, 0, 1, 0]। ব্যাখ্যা: প্রথমে ১ ডিলিট (ইন্ডেক্স ৫), তারপর ২ (ইন্ডেক্স ২), ৩ (ইন্ডেক্স ৩), ৪ (ইন্ডেক্স ০), ৫ (ইন্ডেক্স ১), ৬ (ইন্ডেক্স ০)।

সমাধানের পদ্ধতি (মার্জ সর্ট + ইনভারশন কাউন্ট)

মার্জ সর্টের মেজ ফেজে বাম পার্টিশনের বাকি এলিমেন্টগুলো কতটুকু বড় সেটি কাউন্ট করে larger অ্যারেতে রাখা হয়। পরে (value, larger_count) পেয়ার সর্ট করে larger_count আউটপুট করা হয়।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, 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]
        return solve(nums)

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]