良好的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));

实例

基本上,如果情况是您需要将满足条件的项目移动到容器的"一侧",则分区算法函数应该在要选择的解决方案列表上(如果不是要使用的解决方案).