给定0和1的循环字符串，求最小no。将所有的1s集合在一起

Question

如果给出一个循环(意思是你可以用一个大小为OfString-1的字符串交换0)1和0的字符串，那么显示将所有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);

基于这个答案，这个问题的一个快速解决办法是在某个点上打破圆圈，把它拉伸成一条直线，比方说str，然后把上面的算法应用到它上，然后求出str的最小掉期。假设n是输入循环字符串的长度，那么就有n点可以打破圆圈，这个解决方案的最后一个时间复杂度将是O(n^2)。

所以我试着想出一个解决方案，把O(n)时间复杂度.In --上面的算法--确定为交换是中间1和另一个1's.Since之间的相对距离，我们已经为str计算了最小交换，在其他情况下我们能重用它吗？所以我们不需要做一个for循环来计算最小掉期在每种情况下，那么时间复杂度将是O(n)。

在所有可以打破圆圈的n可能点中，有一些点我们不需要，以100011作为输入的循环字符串，我们在两个不同的点拆分它，一个在索引0和1之间，另一个在1和2之间，然后我们得到：

000111  and  001110

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

为了重用最后的结果，我们在1's之后从左到右有序地打破圆圈，以011010110001为例，首先计算最小掉期，然后在指数1和2之间进行分解，为了简单起见，当我们把圆圈拉伸成一条直线时，我们仍然将数字保持为0's。

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"));

​

Answer 2

找到一个好的起点，并将所有具有相同价值的东西移向该集群。

注意: Python有点生疏，没有设置来测试atm (现在通常使用Ruby )，但是应该非常接近有效的python，如果无效的话。

def longest_cluster_ending_indexes(array)
  # Scan the array to find the end index of the longest cluster of the same value
  index = 0
  check = array[start]
  best_index = 0
  most_count = 1
  count = 1
  for item in array[1:-1]:
    index += 1
    if item == check:
      count += 1
      if count > most_count:
        best_index = index
        most_count = count
      else:
        check = item
        count = 1
   return (best_index - most_count, best_index)

last_seen_left,last_seen_right = longest_cluster_ending_index(array)
check = array[last_seen_right]
index_left = start_left = last_seen_left
index_right = start_right = last_seen_right
swaps = 0
while true:
  index_left -= 1
  if array[index_left] == check
    diff = (index_left - last_seen_left) - 1
    swaps += diff
    last_seen_left -= 1

  if array[index_right] == check
    diff = (index_right - last_seen_right) - 1
    swaps += diff
    last_seen_right += 1

  break if index_left % len(array) == start_right # Went around the array
  break if index_right % len(array) == start_left # Went around the array

我们希望找到一个最长的运行规模，并在运行结束时开始。这防止了这样的情况:如果从索引10000000000000011101开始，0就不会给出不正确的结果。相反，最好从最后0开始，在大的0组中开始。在这种情况下，您只需要在下一个零上做一个交换，就可以向后移动。

性能是O(N)，其中N是0和1的总数。

例子：111000111000

在这里，我们有4次相同大小的跑步。算法应该确定索引2是最好的起点(第一组结束)。它会扫描，找到第二组，并将它们逐个移动。掉期为3+3+3= 9。

111100011000 3 swaps. index 7 - index 3 - 1 = 3 swaps (right side)
111110001000 3 swaps. index 8 - index 4 - 1 = 3 swaps (right side)
111111000000 3 swaps. index 9 - index 5 - 1 = 3 swaps (right side)

11101100001
11101100001 # Second to last is starting index
11111000001 # index 3 and index 6, cost is 2 swaps (from the left side)

嗯，这个问题提出了一个很好的观点，算法必须经过调整才能双向地从最好的集群(而不是仅仅向右)搜索，尽管现在它确实完成了它严格需要完成的工作的大约2倍(循环地，它可能在数组的另一端结束)。

01001001100 => left start = 2 (moving left), right start = 3 (moving right)
10000101100 => Swap left and right (cost = 1 + 1 = 2 swaps)
00000011101 => Swap left and right (cost = 1 + 1 = 2 swaps)
00000011110 => One more swap
So 5 swaps.

011010110001 => Left start at 8, right start and the last index
111011100000 => 2 swaps and 1 swap = 3 swaps
011111100000 => 3 swaps
6 swaps