2459.Sort-Array-by-Moving-Items-to-Empty-Space

首先，我们发现，无论最终是要把0放在首位还是末位，都不影响操作的本质。对于后者，如果我们将nums的最后一个元素虚拟地认为是在head的位置，那么操作的方法完全可以与前者归并处理。即

    vector<int>nums2(nums.begin(), nums.end()-1);
    nums2.insert(nums2.begin(), nums.back());
    return min(helper(nums), helper(nums2));     

其次，我们考虑如何实现上述的helper函数，即将nums里的元素排序为0,1,2,...,n-1.

我们容易想到贪心的策略：如果当前的0在位置i且i!=0，那么我们必然将i拿过来交换一次使之归位。然后继续看此时0所在的位置j，如果仍然j!=0，那么同样必然把j拿过来使之归位。接着继续查看0，直至0到了队首。我们发现，可以用k次操作，将k+1个元素（包括0）归到正确的位置。这k+1个元素本质上val-index构成了一个环。

其实有另外一种等效的归位操作，我们称之为index sort：只盯着index=0上的数i，如果它不是0，那么就把它与nums[i]交换使得i归位；再看此时index=0上的数j，如果它还不是0，继续将其与nums[j]交换使得j归位。直至index=0上的数变成0. 同样的结论：如果交换了k次，意味着我们已经将k+1个元素（包括0）归到正确的位置。

接下来我们看其他的位置。如果某个位置i上的数字不是i，我们同样用上面的方法，通过若干次交换使得位置i上得到i。例如：

idx:  1 2 3
val:  3 1 2

第一次操作后：

idx:  1 2 3
val:  2 1 3

第二次操作后：

idx:  1 2 3
val:  1 2 3

但是注意到这两次操作我们都没有利用到0，这是不符合要求的。那么该如何通过0来实现呢？其实只要开头增加一步，将之前已经归位的0与位置1上的元素再交换，即额外增加了一个没有归位的0：

idx:  0 1 2 3
val:  3 0 1 2

我们发现此时val-index的环上有四个元素了，同上的理论，我们只需要做三次index sort就能将这四个元素归位。加上之前额外的一次操作，总共是四次。

于是得出结论：如果某个非0的位置i上的数字不是i，并且通过k次交换（index sort）可以使得位置i上出现i的话，那么实际上借助0的话，我们需要k+2次交换（index sort）来实现。

综上：我们对每个位置i尝试index sort，假设k次操作后能够将数值i出现在位置i上，那么(1) 如果i是0，我们就将总操作数增加k；(2)如果i不是0，我们将总操作数增加k+2.