良好的C ++解决方案可以“将所有零归到数组的后面”。面试挑战 [英] Good C++ solutions to the "Bring all the zeros to the back of the array" interview challenge

问题描述

我接受了一次Jr.开发工作的面试，他要我编写一个程序，该程序需要一系列整数并将零推到后面。这里是约束条件（他一开始并没有告诉我...。在编程访谈中经常发生，我在解决问题时就了解了问题的约束条件，哈哈）：

I had an interview for a Jr. development job and he asked me to write a procedure that takes an array of ints and shoves the zeroes to the back. Here are the constraints (which he didn't tell me at the beginning .... As often happens in programming interviews, I learned the constraints of the problem while I solved it lol):

• 必须就地执行；无需创建临时数组，新数组等。


• 不必保留非零数字的顺序（我希望他一开始会告诉我）
>

• Have to do it in-place; no creating temporary arrays, new arrays, etc.
• Don't have to preserve the order of the nonzero numbers (I wish he would've told me this at the beginning)

设置：

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);

还有什么其他好的答案？

What are some other good answers?

推荐答案

也许面试官正在寻找以下答案：

Maybe the interviewer was looking for this answer:

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

如果需要保留订单，则 std :: stable_partition ：

If the order needs to be preserved, then std::stable_partition should be used:

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

对于C ++ 11之前的版本：

For pre C++11:

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

实时示例

基本上，如果情况是您需要将满足条件的项目移动到容器的一侧，则使用分区算法功能应在要选择的解决方案列表中处于较高位置（如果不是要使用的解决方案）。

Basically, if the situation is that you need to move items that satisfy a condition to "one side" of a container, then the partition algorithm functions should be high up on the list of solutions to choose (if not the solution to use).

这篇关于良好的C ++解决方案可以“将所有零归到数组的后面”。面试挑战的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！