পাইথনে সিকোয়েন্স সর্ট করার জন্য প্রয়োজনীয় ন্যূনতম সওয়াপের সংখ্যা বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে বরাবর নয় এমন একটি সংখ্যার তালিকা আছে; আমাদের কাজ হল তালিকাটি ক্রমবর্ধমান ক্রমে সর্ট করার জন্য প্রয়োজনীয় ন্যূনতম সওয়াপের সংখ্যা বের করা।

উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [3, 1, 7, 5], তবে আউটপুট হবে 2, কারণ আমরা ৩ এবং ১ কে সওয়াপ করে, তারপর ৫ এবং ৭ কে সওয়াপ করে সর্ট করা যাবে।

• sort_seq := nums কে সর্ট করা তালিকা
• table := একটি নতুন ম্যাপ (ডিকশনারি)
• nums-এ প্রতিটি ইনডেক্স i এবং ভ্যালু n এর জন্য, table[n] := i সেট করুন।
• swaps := 0
• i কে ০ থেকে len(nums) পর্যন্ত লুপ চালান:
  • n := nums[i]
  • s_n := sort_seq[i]
  • s_i := table[s_n]
  • যদি s_n != n হয়, তবে:
    • swaps := swaps + 1
    • nums[s_i] := n
    • nums[i] := s_n
    • table[n] := s_i
    • table[s_n] := i
• swaps রিটার্ন করুন।

class Solution:
    def solve(self, nums):
        sort_seq = sorted(nums)
        table = {}
        for i, n in enumerate(nums):
            table[n] = i
        swaps = 0
        for i in range(len(nums)):
            n = nums[i]
            s_n = sort_seq[i]
            s_i = table[s_n]
            if s_n != n:
                swaps += 1
                nums[s_i] = n
                nums[i] = s_n
                table[n] = s_i
                table[s_n] = i
        return swaps

ob = Solution()
nums = [3, 1, 7, 5]
print(ob.solve(nums))

[3, 1, 7, 5]

2