最小交換操作

Question

陣列a []只包含1和0的。

我們希望通過交換位置來獲得連續的1的（大於或等於n）的序列。

如何在最小交換操作中執行此類任務。

我們可以交換任意兩個職位。需要

這裏輸出最小數目交換操作以創建更大的連續段或從數組a []等於n 1的。

數組長度< = 10^5。

對於從前面示例 -

INPUT: 

a[5]={1,0,1,0,1} 

n=2 

OUTPUT: 

1 

Answer 1

從左邊經過數組，跟蹤位於當前位置左側的n位置的1的計數。

對於每個元素，如果它是1，則增加一個計數器，如果位於左邊的元素是1，則減少計數器，這可以很容易地完成。

現在我們所需要做的就是跟蹤以上最大數量 - n - this將是交換的最小數量。

噢，我們可能應該經過並檢查數組中是否有實際的n 1。

這將花費O(n)。

Answer 2

掃描，直到你得到一個0，然後從後面掃描，直到你得到一個1交換他們。交換是必要的，應該清楚的是，這兩個元素不需要再次交換。重複從當前位置開始的過程，直到參考指標在中間相遇。

所有必要的交換都將完成，每個需要交換的元素只會發生一次。我看不出你怎麼做比這更少的掉期。

Answer 3

按照我的理解，您嘗試使用最小交換次數將a[4]={1,0,1,0}排列到a[4]={1,1,0,0}。

也許這可能不需要像下面

int a[4]={1,0,1,0} 

for(int i=0;i<a.length;i++) 
{ 
if(a[i] == 1 && a[i+1] != a[i+2]) 
{ 
a[i+1] = a[i+1]+a[i+2]; 
a[i+2] = a[i+1]-a[i+2]; 
a[i+1] = a[i+1]-a[i+2]; 
} 
} 

Answer 4

以1和0的陣列的任何交換。我們希望找到具有n個1組成的連續序列落得需要交換數目：

1, 0, 1, 0, 1, 1 

有此數組4個可能最後的安排。交換次數所需 每個佈置是原始數組中，在最終陣列中的相同的位置爲1是 0的個數：

1, 1, 1, ?, ?, ? - 1 swap 
?, 1, 1, 1, ?, ? - 2 swaps 
?, ?, 1, 1, 1, ? - 1 swap 
?, ?, ?, 1, 1, 1 - 1 swap 

這可以在線性時間內通過創建兩個找到數組：在任何索引左邊的0的數目和在任何索引的右邊的0的數目的0的總數 。遍歷所有可能的最終安排，並且 通過從這兩個 數組中添加適當的值來計算掉期次數。