পাইথনে ক্রম সাজানোর জন্য প্রয়োজনীয় অদলবদলের সংখ্যা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে স্বতন্ত্র সংখ্যার একটি তালিকা আছে; ক্রমবর্ধমান ক্রমে তালিকা বাছাই করার জন্য আমাদের ন্যূনতম সংখ্যক অদলবদল করতে হবে।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[3, 1, 7, 5], তাহলে আউটপুট হবে 2, যেমন আমরা 3 এবং 1, তারপর 5 এবং 7 অদলবদল করতে পারি।

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

• sort_seq :=তালিকার সংখ্যা সাজান
• টেবিল :=একটি নতুন মানচিত্র
• প্রতিটি সূচক i এবং n এর মান সংখ্যার জন্য, করুন
  • টেবিল[n] :=i
• অদলবদল :=0
• আমি 0 থেকে সংখ্যার আকারের মধ্যে,
  করুন
  • n :=সংখ্যা[i]
  • s_n :=sort_seq[i]
  • s_i :=টেবিল[s_n]
  • যদি s_n n এর মত না হয়, তাহলে
    • swaps :=swaps + 1
    • সংখ্যা[s_i] :=n
    • সংখ্যা[i] :=s_n
    • টেবিল[n] :=s_i
    • টেবিল[s_n] :=i
• রিটার্ন অদলবদল

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

উদাহরণ কোড

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