增加迭代变量背后的直觉是什么？

Question

增加迭代变量背后的直觉是什么？

c++algorithm

3

我正在解决LeetCode.com上的一个问题：

给定一个有n个红、白或蓝色物体的数组，将它们就地排序，使相同颜色的物体相邻，并按照红、白和蓝色的顺序排列。在这里，它们使用整数0、1和2来表示红、白和蓝色。[不能使用平凡的计数排序]。

对于输入：[2,0,2,1,1,0]；期望输出为：[0,0,1,1,2,2]。

其中之一高度赞成的解决方案如下：

   public void sortColors(vector<int>& A) {
       if(A.empty() || A.size()<2) return;
       int low = 0; 
       int high = A.size()-1;
       for(int i = low; i<=high;) {
           if(A[i]==0) {
              // swap A[i] and A[low] and i,low both ++
              int temp = A[i];
              A[i] = A[low];
              A[low]=temp;
              i++;low++;
           }else if(A[i]==2) {
               //swap A[i] and A[high] and high--;
              int temp = A[i];
              A[i] = A[high];
              A[high]=temp;
              high--;
           }else {
               i++;
           }
       }
   }

我的问题是，为什么当A[i]==0和A[i]==1时i被递增，而A[i]==2时不递增？使用纸笔算法可以得出答案，但你能否提供一些直觉上的解释呢？

谢谢！

- P.K.

在纸上演示一遍以找出原因。 - tadman

2

@tadman，是的，我试过了，它可以使用。但是我不明白为什么要这样做的直觉。:( - P.K.

1

它只是将所有的“0”（红色）移动到数组的底部，将所有的“2”（蓝色）移动到顶部，默认情况下，“1”（白色）保留在中间。 - David C. Rankin

2个回答

2

也就是说，对于0和1来说，只处理左边已经被检查/排序过的项目。而对于从数组右端开始的2来说，则需要处理尚未被检查过的项目。更具体地说，在这个例子中，只处理三种不同的状态：

1. 当前正在审查的项目等于0：在这种情况下，排序算法会将此项目放在所有已排序的零（即A[low]）的末尾。之前在A[low]处的项目只能是0或1（因为它们已经排序），这意味着可以与当前项目交换而不会破坏顺序。到目前为止，从A[0]到A[i]的每个项目都已经排序，因此下一个要审查的项目将是A[i + 1]，因此i++。

2. 当前项目等于1：在这种情况下，不需要进行交换，因为所有的0和1都已经放在A[0]到A[i-1]中，所有的2也已经放在数组的末尾。这意味着下一个要审查的项目是A[i + 1]，因此i++。

3. 当前项目等于2：在这种情况下，当前项目将被放置在数组的末尾，靠近（即在左侧）所有其他已排序的2（即A[high]）。将从A[high]到A[i]交换的项目尚未排序，因此必须在下一步中进行审查，因此i = i。

- n00ne

谢谢你的回答。一个问题 - “当前项将放置在数组的末尾，以便与已排序的所有其他2（A [high]）相匹配” - 实际上不是应该放在所有“2”的左边吗？ - P.K.

1

是的！绝对正确。它将被放置在所有2的末尾的左侧一个位置。当前驻留在那里的项目因此具有未知值（可能为0、1或2），这就是为什么它仍然需要被处理的原因。 - n00ne

明白了。谢谢！ - P.K.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- k_ssb · Accepted Answer

这段代码遍历数组并维护了约束条件，即元素0..i已排序，全部是0或1。（之前存在的2被交换到数组末尾。）

当A[i]==0时，你将在i处的元素（我们刚才说过是0）与在范围0..i中第一个1元素（如果有的话）处的元素low交换。因此，交换后，A[i]==1，这是正确的（约束仍然有效）。现在我们可以安全地向数组前进了。如果A[i]==1，则不进行交换。

当A[i]==2时，你实际上是将元素i（我们刚才说过是2）移动到数组末尾。但是，你还要将数组末尾的某个元素移动到元素i的位置，而且我们不知道那个元素是什么（因为我们没有在之前处理过，不像A[i]==0的情况）。因此，我们不能安全地将i向前移动，因为A[i]处的新元素可能还没有到正确的位置��我们需要另一个迭代来处理新的A[i]。