string - 给定一个由 0 和 1 组成的圆形字符串,求最小编号。将所有 1 放在一起的相邻掉期

原文 标签 string algorithm sorting

如果给定一个循环(意味着您可以用 sizeOfString-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 字符串的最小相邻交换数?

最佳答案

所以我受到 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's .因为我们已经计算了 str 的最小掉期,有什么办法可以在其他情况下重用它?
所以我们不必在每种情况下都进行 for 循环来计算最小交换,那么时间复杂度将为 O(n) .
全部n我们可以打破圆圈的可能点,有些点我们不需要,取100011作为输入的循环字符串,我们在两个不同的点将其断开,一个在索引 0 之间。和 1 , 另一个在 1 之间和 2 ,那么我们将得到:
000111  and  001110
在上述算法中,我们只需要计算相对距离 来自其他1's到中间1 ,在这两种情况下,决定最小掉期的是它们的包含所有 1's 的公共(public)子字符串 ,即 111 .所以为了避免这种我们重复计算相同结果的情况,我们只在每个 1's 之后立即打破循环。 .
为了重用最后一个结果,我们在 1's 之后立即断开圆圈。从左到右有序,取011010110001例如,我们首先计算最小掉期,然后在索引 1 之间进行拆分。和 2 ,为简单起见,当我们把圆拉成直线时,我们仍然保持在我们打破圆的点之前的数字为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"));

关于string - 给定一个由 0 和 1 组成的圆形字符串,求最小编号。将所有 1 放在一起的相邻掉期,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64441370/

相关文章:

java - 尝试按列表项对 HashMap<String, List<String>> 进行排序

sorting - 如何在Groovy中对文本+日期字符串列表进行排序

cocoa - 帮助跨两个属性对NSArray进行排序(使用NSSortDescriptor?)

php - PHP中二维数组中的唯一数组

java - 如何在java中检查两个用户定义的对象

c++ - 如何使用string::find与整数? C++

.net - ASP.NET VB-.NET的一些数学运算

java - 在没有额外空间的情况下在 O(n) 中反转堆栈不会发生

python - Python 中的可变字符串

java - Java URL正则表达式不匹配