c++ - 将数组中的零移动到末尾

Question

“这个问题属于“数组转换”的大类。这一类是技术面试的重点。主要是因为数组是如此简单易用的数据结构。遍历或表示不需要任何样板代码并且您的大部分代码看起来都像伪代码本身。

问题的 2 个要求是:

将所有的 0 移动到数组的末尾。

所有非零元素必须保持其原始顺序。"

我的想法:找到零并将它们的位置与最后的数字交换

       /* int swap;
       int n=nums.size()-1;
       for(int i=0;i<nums.size();i--){
           if(nums[i]==0){
               swap = nums[i];
               nums[i] = nums[n];
               nums[n] = swap;
               n--;
           }

       }

我的输入[0,1,0,3,12]输出[1,3,12,0,0]差异预期的[1,3,12,0,0]

我不知道为什么正确答案(部分)是:

 (int n = 0, cur = 0; cur < nums.size(); cur++) {
        if (nums[cur] != 0) {
            swap(nums[n++], nums[cur]);
         }
       }
    }

Answer 1

你能使用标准库吗？ std::stable_partition()让它变得微不足道。有点像

std::stable_partition(nums.begin(), nums.end(),
    [](const auto &n){ return n != 0; });

---

关于您帖子中的解决方案如何工作的问题:

第一次迭代开始时，n为0，cur为0，nums为[0,1,0,3,12]。 nums[cur] 为 0，所以没有任何反应。在第二次迭代开始时，cur 为 1，而 nums[cur] 为 1，因此发生了 n 的交换和递增。

现在 n 为 1，cur 为 2，nums 为 [1,0,0,3,12]。 nums[cur] 为 0，因此在第三次迭代中没有任何反应。在第四次迭代中，cur 现在为 3，发生了交换。所以在第 5 次迭代开始时，n 为 2，cur 为 4，nums 为 [1,3,0,0,12]。我将留给您解决该步骤中发生的情况。

基本上，当 n 不等于 cur 时，它是一个 0 元素的索引，可以与 cur 是其索引的非 0 元素交换。这种交换最终会将全 0 移动到末尾。