मान लीजिए हमारे पास एक बाइनरी ऐरे data है, हमें ऐरे में कहीं भी सभी 1 को एक साथ ग्रुप करने के लिए आवश्यक न्यूनतम स्वैप्स की संख्या ढूंढनी है। इसलिए यदि ऐरे [1,0,1,0,1,0,0,1,1,0,1] जैसा है, तो आउटपुट 3 होगा, जैसे संभावित समाधान [0,0,0,0,0,1,1,1,1,1,1]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- one := 0 सेट करें, n:= data ऐरे की लंबाई
- आकार n का एक ऐरे summ बनाएं, और इसे 0 से भरें, summ[0] := data[0] सेट करें
- one := one + data[0]
- i को 1 से n - 1 तक रेंज में
- summ[i] := summ[i - 1] + data[i]
- one := one + data[i]
- ans := one
- left := 0, right := one - 1
- जब तक right < n
- यदि left 0 है, तो temp := summ[right], अन्यथा temp := summ[right] - summ[left - 1]
- ans := ans और one - temp का न्यूनतम
- right और left को 1 से बढ़ाएं
- ans लौटाएं
उदाहरण (पायथन)
बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -
class Solution(object):
def minSwaps(self, data):
one = 0
n = len(data)
summ=[0 for i in range(n)]
summ[0] = data[0]
one += data[0]
for i in range(1,n):
summ[i] += summ[i-1]+data[i]
one += data[i]
ans = one
left = 0
right = one-1
while right < n:
if left == 0:
temp = summ[right]
else:
temp = summ[right] - summ[left-1]
ans = min(ans,one-temp)
right+=1
left+=1
return ans
ob = Solution()
print(ob.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))इनपुट
[1,0,1,0,1,0,0,1,1,0,1]
आउटपुट
3