生成稀疏向量的置换

说我试图生成[21 2 0 34 0 0 0 1]的置换，它将移动最后的所有零（请记住零的数量可能很大，将其视为稀疏向量）矢量的非零值将在矢量的前面移动，而不会改变它们的自然顺序。结果将是[21 2 34 1 0 0 0 0 ]。什么是这对大载体这种计算效率的解决方案：生成稀疏向量的置换

去了载体和添加到另一个向量非零的元素，然后用零填充第二向量的休息吗？
生成给出的向量所有排列（他们大概n!/m!其中n是向量的长度和m是零的个数，如果我们忽略非零元素可能出现一次以上的号码）和选择适合此限制的组合。

来源

2011-11-04 hyperboreean

你忘BOGO排序的选项3.严重的是，它从来没有计算效率创造的东西所有排列，即使你认为N - m小。 – Gleno

简单地遍历向量并将每个项目与零比较。如果它为零，请记住它的索引。如果它不是零，并且您记住空白字段的索引，请将其移到那里并更改您记忆的索引。需要线性时间并且只需要一个额外存储单元。我想不出任何更有效的方法来做到这一点。

来源

2011-11-04 12:21:53

注意，在一个稀疏向量中会存在连续的零，所以一个简单的单元格保持零索引是不够的。您将需要一个向量来保存零索引。 – pnezis

不，一旦您将一个项目移动到第一个零单元格，您就知道下一个零单元格没有看到的位置。尝试一些棋盘游戏的数字... –

是的，你是对的... – pnezis

最有效的解决方案是遍历向量并移动零前的所有非零数字。该算法类似于STL的stable_partition算法，pred等于'elem！= 0'。

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

来源

2011-11-04 12:22:26

从你的建议的解决方案显然是第一个是速度更快，因为它运行在相反的为O（n）到为O（n！）第二个的运行时间。为了避免外部存储器的使用，我可以建议对其进行一些改进：

保留两个指针：i指向第一个零位，而j只是对矢量进行迭代。在每个步骤中，如果v[ j ] != 0将其值设置为i-位置并且增加i。因此，您将无需额外的内存。此外，在这种方式将执行准确N + non_zero_elements_qty迭代中，而在解决方案1的迭代数量为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 ];

来源

2011-11-04 12:28:02

生成稀疏向量的置换

回答

相关问题