पायथन में अनुक्रम को सॉर्ट करने के लिए आवश्यक स्वैप्स की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास अलग-अलग संख्याओं की एक सूची है; हमें सूची को बढ़ते क्रम में सॉर्ट करने के लिए आवश्यक न्यूनतम स्वैप्स की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट nums = [3, 1, 7, 5] है, तो आउटपुट 2 होगा, क्योंकि हम 3 और 1 को स्वैप कर सकते हैं, फिर 5 और 7 को।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• sort_seq := nums को सॉर्ट करें
• table := एक नया मैप
• प्रत्येक इंडेक्स i और मान n के लिए nums में:
  • table[n] := i
• swaps := 0
• i को 0 से 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