应对"Bring all the zeros to the back of the array"面试挑战的良好C++解决方案

Question

我面试了Jr.的开发工作，他让我写一个过程，这个过程接受一个整数数组，把零推到后面。这是限制（他一开始没有告诉我....正如编程面试中经常发生的那样，我在解决问题时了解了问题的约束，哈哈）：

• 必须就地执行此操作;无需创建临时数组、新数组等。
• 不必保留非零数的顺序（我希望他一开始就告诉我这一点）

设置：

int arr[] = {0, -2, 4, 0, 19, 69}; 
/* Transform arr to {-2, 4, 19, 69, 0, 0} or {69, 4, -2, 19, 0, 0} 
   or anything that pushes all the nonzeros to the back and keeps
   all the nonzeros in front */

我的回答：

bool f (int a, int b) {return a == 0;}
std::sort(arr, arr+sizeof(arr)/sizeof(int), f);

还有哪些其他好的答案？

Answer 1

也许面试官正在寻找这个答案：

#include <algorithm>
//...
std::partition(std::begin(arr), std::end(arr), [](int n) { return n != 0; });

如果需要保留顺序，则应使用std::stable_partition：

#include <algorithm>
//...
std::stable_partition(std::begin(arr), std::end(arr), [](int n) { return n != 0; });

对于 C++11 之前：

#include <functional>
#include <algorithm>
//...
std::partition(arr, arr + sizeof(arr)/sizeof(int), 
               std::bind1st(std::not_equal_to<int>(), 0));

现场示例

基本上，如果

情况是您需要将满足条件的项目移动到容器的"一侧"，那么分区算法函数应该在要选择的解决方案列表中排在前面（如果不是要使用的解决方案）。

Answer 2

排序

的方法是O（N*Log₂N）。有一个线性解决方案是这样的：

• 设置两个指针 - readPtr 和 writePtr，最初指向数组的开头
• 创建一个循环，从数组readPtr到最后。如果*readPtr不为零，则复制到*writePtr，并推进两个指针;否则，仅前进readPtr.
• 一旦readPtr位于数组的末尾，writePtr走到数组的末尾，同时将零写入其余元素。

Answer 3

这是

O（n），所以这可能是他正在寻找的：

auto arrBegin = begin(arr);
const auto arrEnd = end(arr);
for(int i = 0; arrBegin < arrEnd - i; ++arrBegin){
    if(*arrBegin == 0){
        i++;
        *arrBegin = *(arrEnd - i);
    }
}
std::fill(arrBegin, arrEnd, 0);