生成稀疏向量的置換

說我試圖生成[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

生成稀疏向量的置換

回答

相關問題