生成稀疏向量的置换

Question

假设我正在尝试生成一个[21 2 0 34 0 0 0 1]的置换，它将在最后移动所有的零(请记住，零点的数目可能很大，把它看作是一个稀疏的向量)，而非零值将在向量的前面移动，而不改变它们的自然顺序。结果是[21 2 34 1 0 0 0 0 ]。对于这类大型向量来说，什么是计算效率高的解决方案：

1. 遍历向量，将非零元素添加到另一个向量中，然后用零填充第二个向量的其余部分？
2. 为给定的向量生成所有的排列(它们大致是n!/m!，其中n是向量的长度，m是零的数目，如果我们忽略可能不止一次出现的非零元素的数量)，然后选择符合这一限制的组合。

Answer 1

只需在向量上迭代，并将每一项都比较为零。如果为零，请记住它的索引。如果它不是零，并且您正在记住一个空字段的索引，那么将它移到那里并更改您记忆中的索引。需要线性时间，只需要一个额外的存储单元。我想不出比这更有效的方法了。

Answer 2

最有效的解决方案是在向量上迭代，并将所有非零数移到零前面。该算法类似于STL的隔断算法，pred = 'elem != 0‘。

但是如果你需要保持原来的向量，你的第一个想法似乎是最优的。为了清楚起见，在这种情况下，您应该在处理整个向量之前为整个向量分配内存，并相应地填充其元素，而不是在每次迭代时将新元素添加到向量的末尾。

Answer 3

从建议的解决方案中可以看出，第一个解决方案速度更快，因为它运行O(n)与第二个解决方案的O(n!)运行时相反。为了避免外部内存的使用，我可以建议对其进行一些改进：

保持两个指针:指向第一个零位置的i和只在向量上迭代的j。在每一步中，如果v[ j ] != 0将其值放到i-th位置并增加i。在此，您将不再需要额外的内存。同样，您将精确地执行N + non_zero_elements_qty迭代，而在您的解决方案中，迭代量是N + zero_elements_qty，它仍然是O(n)，但是如果向量相当稀疏，则可能会慢一些。

下面是C++中的一个可能的实现：

// input vector<int> v
int n = v.size();
int i = 0;
while( v[ i ] != 0 ) ++i;
for( int j = 0; j < n; ++j )
   if( v[ j ] != 0 )
      v[ i++ ] = v[ j ];