string - 给定一个由 0 和 1 组成的循环字符串，求最小值。将所有 1 放在一起的相邻交换

Question

如果给定一个由 1 和 0 组成的循环(这意味着您可以将 0 与 sizeOfString-1 交换)字符串，有什么好的算法可以显示将所有 1 组合在一起所需的最少相邻交换数。 1 不需要在字符串中的任何特定位置分组。它们只需要在提供最少数量的相邻交换的任何位置进行分组。

例如，如果字符串看起来像这样......

011010110001

相邻交换的最小数量为 6，因为您将进行以下交换:

交换索引 0 和 11，得到:111010110000

交换索引 3 和 4，得到:111100110000

交换索引 5 和 6，得到:111101010000

交换索引 4 和 5，得到:111110010000

交换索引 6 和 7，得到:111110100000

交换索引 5 和 6，得到:111111000000

谁有好的算法可以找到任何 1 和 0 的字符串的最小相邻交换数？

Answer 1

所以我受到了 this answer 的启发，请先看那个答案，它所属的题和这个基本一样，只是这个题的输入字符串是循环的。该答案的关键思想是，为了找到最小交换以对所有 1 进行分组，我们只需要获取所有 1 的索引的数组，该数组的中心将始终保持中心索引，然后通过以下算法计算最小交换，时间复杂度为O(n):

oneIndices = array of indices of all 1's in the input
middleOfOnesIndices = round(oneIndices.length/2)-1    // index to the center index
minimumSwaps = 0
foreach index i of oneIndices
    minimumSwaps += aboluteValue(oneIndices[middleOfOneIndices]-oneIndices[i])-absoluteValue(middleOfOneIndices-i);

根据那个答案，这个问题的一个快速解决方案是在某个点打破圆圈并将其拉伸(stretch)成一条直线，比方说 str，然后将上面的算法应用于它， 然后我们 找到 str 的最小交换。令n为输入循环字符串的长度，则有n个点可以破环，最终该解法的时间复杂度为O (n^2).

所以我试图想出一个时间复杂度为 O(n) 的解决方案。在上面的算法中，决定交换的是中间 1< 之间的相对距离 和其他 1。由于我们已经计算了 str 的最小交换，有什么方法可以在其他情况下重用它吗？ 所以我们不必做一个 for 循环来计算每种情况下的最小交换，那么时间复杂度将是 O(n)。

在所有n个我们可以打断圆的点中，有一些点我们不需要，将100011作为输入的圆字符串，我们打断它在两个不同的点，一个在索引 0 和 1 之间，另一个在 1 和 2 之间，那么我们将得到:

000111  and  001110

在上述算法中，我们只需要计算其他1到中间1的相对距离，在这两种情况下，决定最小交换的是它们的包含所有1的公共(public)子串，即111。因此，为了避免重复计算相同结果的这种情况，我们只在每个 1 之后立即打破圆圈。

为了重用上一个结果，我们从左到右依次打破1之后的圆圈，以011010110001为例，我们首先计算最小交换，然后打破它在索引 1 和 2 之间，为了简单起见，当我们将圆拉伸(stretch)成一条直线时，我们仍然将我们所在点之前的数字保留为 0打破圈子。

011010110001   <---before
00101011000101 <---after break it between indices 1 and 2
^^  <--- these two 0's actually don't exist, but to keep the indices of 1's to it's right 
         as unchanged, so we can reuse last result handily.

the array of all indices of 1's: 
[1,2,4,6,7,11]  <----before
[2,4,6,7,11,13] <----after break it between indices 1 and 2

我用 javascript 编写的最终解决方案具有 O(n) 时间复杂度:

function getOneIndices(inputString) {
    var oneIndices = [];
  for (var i=0; i<inputString.length; i++) {
    if (inputString.charAt(i) === "1") {
        oneIndices.push(i);
    }
  }
  return oneIndices;
}

function getSwapInfo(inputString) {
  var oneIndices = getOneIndices(inputString);
  
  if(oneIndices.length < 2) return 0;
  
  var minSwaps = Number.MAX_VALUE;
  var distanceInInput = 0, distanceInOneIndices = 0;
  
  var middleOfOneIndices = Math.round(oneIndices.length/2)-1;
  
  for (var i=0; i<oneIndices.length; i++) {
    distanceInInput += Math.abs(oneIndices[middleOfOneIndices]-oneIndices[i]);
    distanceInOneIndices += Math.abs(middleOfOneIndices-i);
  }
  
  for(var i = 0, lastOneIndexMoved = -1, endIndexInInput = inputString.length - 1; 
                                        i <= oneIndices.length; i++){
    var curSwaps = distanceInInput - distanceInOneIndices;
    if(curSwaps < minSwaps) minSwaps = curSwaps;
    
    var lastMiddleIndex = oneIndices[middleOfOneIndices];
    
    //move the first 1 to the end as we break the circle after it.
    var firstOneIndex = oneIndices[0];
    oneIndices.splice(0, 1);
    var lastOneIndex = endIndexInInput + firstOneIndex - lastOneIndexMoved;
    oneIndices.push(lastOneIndex);
    
    //when we move one step further, the index of the center also move one step further,
   // but the length of the indices array of 1's doesn't change, we don't 
   //need to do middleOfOneIndices++
    var diff = oneIndices[middleOfOneIndices] - lastMiddleIndex;
    
    distanceInInput += middleOfOneIndices * diff 
                  - (oneIndices.length - middleOfOneIndices - 1) * diff
                  - Math.abs(lastMiddleIndex - firstOneIndex)
                  + Math.abs(oneIndices[middleOfOneIndices] - lastOneIndex);
    
    lastOneIndexMoved = firstOneIndex;
    endIndexInInput = lastOneIndex;
  }

    return minSwaps;
}

console.log("minimum swaps for '111111': " + getSwapInfo("111111"));
console.log("minimum swaps for '111011': " + getSwapInfo("111011"));
console.log("minimum swaps for '010001': " + getSwapInfo("010001"));
console.log("minimum swaps for '011010110001': " + getSwapInfo("011010110001"));
console.log("minimum swaps for '10000000000000011101': " + getSwapInfo("10000000000000011101"));
console.log("minmum swaps for '01001001100': " + getSwapInfo("01001001100"));