मान लीजिए हमारे पास nums नामक एक ऐरे है और हमें nums को किसी भी क्रम में, या तो आरोही या अवरोही, सॉर्ट करने के लिए आवश्यक स्वैप की संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट nums = [2, 5, 6, 3, 4] है, तो आउटपुट 2 होगा क्योंकि प्रारंभ में nums में [2, 5, 6, 3, 4] है। यदि हम संख्या 6 और 4 को स्वैप करते हैं, तो ऐरे [2,5,4,3,6] बन जाएगा। फिर, यदि हम संख्या 5 और 3 को स्वैप करते हैं, तो ऐरे [2,3,4,5,6] बन जाएगा। तो आरोही क्रम में ऐरे को सॉर्ट करने के लिए 2 स्वैप की आवश्यकता है।
हल करने के चरण
swap_count()फ़ंक्शन परिभाषित करें। यहinput_arrलेगा:pos :=नई सूची जिसमें प्रत्येक आइटम के लिए टुपल्स(item_position, item)हों।posसूची कोinput_arrमें आइटम के अनुसार सॉर्ट करें।cnt := 0indexको 0 सेinput_arrके आकार तक लूप चलाएं:- व्हाइल
Trueलूप चलाएं:- यदि
pos[index][0] == index, तो लूप से बाहर निकलें। - अन्यथा,
cnt := cnt + 1,swap_index := pos[index][0],pos[index]औरpos[swap_index]के मानों को स्वैप करें।
- यदि
- व्हाइल
cntवापस करें।
- मुख्य फ़ंक्शन से, निम्नलिखित करें:
min(swap_count(input_arr), swap_count(input_arr[::-1]))वापस करें।
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def swap_count(input_arr):
pos = sorted(list(enumerate(input_arr)), key=lambda x: x[1])
cnt = 0
for index in range(len(input_arr)):
while True:
if pos[index][0] == index:
break
else:
cnt += 1
swap_index = pos[index][0]
pos[index], pos[swap_index] = pos[swap_index], pos[index]
return cnt
def solve(input_arr):
return min(swap_count(input_arr), swap_count(input_arr[::-1]))
nums = [2, 5, 6, 3, 4]
print(solve(nums))
इनपुट
[2, 5, 6, 3, 4]
आउटपुट
2