Python中將所有1分組的最小交換次數

假設我們有一個二進位制陣列資料，我們需要找到將陣列中所有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 := 資料陣列的長度
  • 建立一個大小為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

示例（Python）

讓我們來看下面的實現，以便更好地理解：

 線上演示

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

更新於：2020年4月30日

261 次檢視

開始您的職業生涯

完成課程獲得認證

開始學習
廣告