生成稀疏向量的排列
假设我正在尝试生成 [21 2 0 34 0 0 0 1] 的排列，它将移动末尾的所有零（请记住，零的数量可能很大，想想向量的稀疏向量）和非零值将在向量的前面移动，而不改变它们的自然顺序。结果将是[21 2 34 1 0 0 0 0]。对于这种大型向量来说，计算效率高的解决方案是什么：
- 遍历向量并将非零元素添加到另一个向量，然后用零填充第二个向量的其余部分？
- 生成给定向量的所有排列（它们大致为
n!/m!，其中n是向量的长度，m是零的数量（如果我们忽略可能出现多次的非零元素的数量）并选择符合此限制的组合。
Say I am trying to generate a permutation of [21 2 0 34 0 0 0 1] that would move all of the zeros at the end (keep in mind that the number of zeros could be big, think of this as a sparse vector) of the vector and the non-zero values would be shifted in the front of the vector, without changing their natural order. The result would be [21 2 34 1 0 0 0 0 ]. What's a solution that's computationally efficient for large vectors of this kind:
- Go over the vector and add to another vector the non-zero elements and then fill the rest of the 2nd vector with zeros?
- Generate all permutations for the given vector (they're roughly
n!/m!wherenis the length of the vector andmis the number of zeros, if we disregard the number of non-zero elements that could appear more than once) and pick the combinations that fits this restriction.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
只需迭代向量并将每个项目与零进行比较即可。如果它为零，请记住它的索引。如果它不为零并且您记住了空字段的索引，请将其移动到那里并更改您记住的索引。花费线性时间并且只需要一个单元的额外存储。我想不出任何更有效的方法来做到这一点。
Simply iterate over the vector and compare every item to zero. If it is zero, remember its index. If it isn't zero and you're remembering the index of an empty field, move it there and change your remembered index. Takes linear time and requires only one cell of additional storage. I can't think of any more efficient way to do this.
最有效的解决方案是迭代向量并将所有非零数字移到零前面。该算法类似于 STL 的 stable_partition 算法，其中 pred 等于 'elem != 0'。
但如果您需要保留原始向量，您的第一个想法似乎是最佳的。需要明确的是，在这种情况下，您应该在处理之前为整个向量分配内存，并随后填充其元素，而不是在每次迭代时将新元素添加到向量的末尾。
The most effective solution is to iterate over the vector and move all non-zero numbers in front of the zeros. This algorithm is analogous to stable_partition algorithm of STL with pred equals to 'elem != 0'.
But if you need to keep the original vector, your first idea seems to be the optimal one. Just to be clear, in this case you should allocate the memory for the whole vector before processing and consequentially fill its elements, instead of adding new elements to the end of the vector on each iteration.
从您建议的解决方案来看，显然第一个解决方案更快，因为它运行 O(n) 的时间与第二个解决方案的 O(n!) 运行时间相反。我可以建议对其进行一些改进，以避免使用外部内存：
保留两个指针：指向第一个零位置的
i和仅迭代向量。在每一步中，如果v[ j ] != 0将其值放入第i位置并增加i。这样你就不需要额外的内存了。同样，通过这种方式，您将精确执行 N + non_zero_elements_qty 次迭代，而在您的解决方案中，1 次迭代数量为 N + Zero_elements_qty，仍然是 O(n)< /strong>，但如果向量相当稀疏，速度可能会更慢。下面是 C++ 中可能的实现：
From your suggested solutions obviously the first one is faster, because it runs O(n) in opposite to O(n!) run time of the second one. I can suggest a bit improvement to it in order to avoid external memory usage:
Keep two pointers:
iwhich points to the first zero position, andjthat just iterates over the vector. At each step, ifv[ j ] != 0put its value toi-th position and increasei. Hereby you will do without additional memory. Also in such way you will perform exactly N + non_zero_elements_qty iterations, while in your solution 1 iterations quantity is N + zero_elements_qty, which is still O(n), but can be slower if the vector is rather sparse.Here is a possible implementation in C++: