了解最小掉期的特定解决方案，以分组所有1＆＃2nd;问题

Question

我正在查看leetcode问题 2134。将所有1分组在一起的最小互换ii ：

a 交换被定义为在数组中取两个不同的位置并交换了它们中的值。

a 圆形阵列定义为一个阵列，我们认为 first 元素和 last 元素为 相邻。

给定二进制循环 array nums，返回将所有1的最小交换数在的任何位置。

一起

我正在尝试研究其他人如何提出自己的解决方案。我遇到了这个特定的逻辑：

class Solution {
    public int minSwaps(int[] nums) {
        // number of ones    
        int cntones=Arrays.stream(nums).sum();
        // worst case answer
        int rslt=nums.length;
        // position lft and figure better value for min/rslt
        int holes = 0;
        for(int i=0;i<cntones;i++) {
            if(nums[i]==0)
                holes++;
        }
        // better value for rslt from lft to rgt
        // up to index of cntones.
        rslt = Math.min(rslt, holes);
        
        // they have a test case with one element 
        // and that trips up if you dont do modulo
        int rgt=cntones % nums.length;
        for(int lft=0;lft<nums.length;lft++) {
            rslt=Math.min(rslt,holes);
            if(nums[lft]!=nums[rgt]) 
                if(nums[rgt]==1)
                    holes--;
                else 
                    holes++;
            rgt=(rgt+1)%nums.length;
        }
        return rslt;
    }
}

1. 为什么最坏的情况是输入数组的长度？ 我在想等一下，最坏的情况不是[0,1,0,1,0,1 ...]，其中0和1交替？你能给我一个例子吗？

2. 我想＃hores在某些情况下可能是一个可能的解决方案，从窗口的固定长度（总1）数计数，但由于我不了解最坏的情况，所以rslt <rslt << /code>来自问题1，下面的线路也使我陷入困境。

     //从LFT到RGT的RSLT的更好价值
   //到Cntones的索引。
   RSLT = Math.min（RSLT，孔）;
    

3. 关于下面的modulo，我不认为cntones可以大于nums.length，而这会一直导致0？我正在考虑使用一个元素的情况，您必须检查一个元素是0还是1。

     //他们有一个带有一个元素的测试用例 
   //如果您不做模仿，那就去了
   int rgt = cntones％nums.length; 
    

4. 由于＃1〜＃3，循环的最后一个对我没有意义...

Answer 1

为什么最坏的情况是输入数组的长度？

首先要说的是，互换只有在以1的价格交换0时才有用。其次，第二次交换相同的数字是没有意义的，因为这种双重交换可以通过单个交换来实现。因此，我们可以说，掉期数量的上限是0位数或1位数的数量（最少）。实际上，这是一个高估，因为至少一个1位应该能够保持不动。但是，让我们暂时忽略这一点。为了达到最坏的情况，应该有多达1个数字，因此我们的长度的一半与最坏的情况一样。当然，通过初始化的价值大于（如长度），我们不会受到伤害。

交替数字的示例将通过保持一半的1位数不动，并在它们之间的孔中移动其余的1位数来解决。因此，这意味着我们有许多互换等于数组长度的四分之一。

下面的线路也使我陷入困境。

  rslt = Math.min（RSLT，孔）;
 

正如您所说，有一个窗口在圆形阵列上移动，这代表了最终的最终情况，所有一位数都应结束。因此，它设定了目标。显然，该窗口内的一位数字无需交换。该窗口内的每个0位数都必须用当前在该窗口外面的1位数交换。这样做将达到目标，因此到达该特定目标窗口的掉期数量等于该窗口内部的孔数（0位数）。

由于每个可能的窗口都进行了练习，因此我们有兴趣找到窗口的最佳位置，即孔数（交换）被最小化的孔数（交换）。这就是这条代码行动。 RSLT是“到目前为止”的最小值，holes是我们对当前窗口的新价值。如果较少，则应将rslt更新到它。这就是在此声明中发生的事情。

关于下面的modulo，我不认为cntones可以大于nums.length，而这会一直导致0？我正在考虑使用一个元素的情况，您必须检查一个元素是0还是1。

  int rgt = cntones％nums.length; 
 

该Modulo仅适用于cntones是等于 nums.length。您是对的，它永远不会超过。但是，可能相等的情况（当输入只有1位数时）。并且由于rgt将用作索引，因此它应该不是等于nums.length，因为这是该插槽大批。

由于＃1〜＃3，循环的最后一个对我没有意义...

从上面的细节中应该可以清楚地清楚。该循环一次每次移动窗口，并保持变量holes逐步更新。当然，我们可以决定计算每个窗口中从头开始的孔数，但这将浪费时间。当我们从一个窗口到另一个窗口时，我们只在左侧丢失一个数字，并在右侧获得一位，因此我们可以使用该信息更新hores，并知道该信息中有多少个孔当前窗口 - 从lft开始并运行（圆形）到rgt的窗口。如果我们在左侧丢失的数字与右边获得的数字相同，那么我们显然没有更改孔的数量。在它们不同的地方，我们要么与上一个窗口相比，要么赢或失去一个洞。