递增迭代变量后的直觉？

Question

我在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++;
           }
       }
   }

我的问题是,为什么i当递增A[i]==0和A[i]==1不何时A[i]==2？使用笔和纸,算法只是给我答案; 但是你能提供一些直觉吗？

谢谢!

Answer 1

这将遍历数组并维护元素0..i排序的约束,以及所有0或者1.(2那里的那些被交换到数组的末尾.)

当A[i]==0你将元素交换到i(我们刚刚说过的0)元素at时low,这是1元素中的第一个元素(如果有的话)0..i.因此,在交换之后,A[i]==1这是正常的(约束仍然有效).我们现在可以安全地在阵列中前进.如果A[i]==1最初也是如此,在这种情况下不执行交换.

什么时候A[i]==2,你基本上将元素i(我们刚才说的那样2)移动到数组的末尾.但是你也在从数组的末尾移动到元素i的位置,我们不知道那个元素是什么(因为我们之前没有处理它,不像这个A[i]==0例子).因此,我们无法安全地i前进,因为新元素A[i]可能尚未出现在正确的位置.我们需要另一个迭代来处理新的A[i].