按索引排列向量

我有兩個向量：向量和索引向量。我怎樣才能讓矢量由索引矢量來排列？像：按索引排列向量

Indexes    5 0 2 1 3 4 
Values     a b c d e f 
Values after operation b d c e f a

索引矢量將始終包含範圍[0, n)和每個索引只有一次。
我需要執行此操作，因爲代碼將在低內存的設備上運行。
我如何在C++中做到這一點？我可以使用C++ 11

來源

2011-11-22 Dani

運行（n）的時間，沒有任何error.Check它你考慮[此相關問題（http://stackoverflow.com/q/236172/1025391）？ – moooeeeep

std::vector<int> indices = { 5, 0, 2, 1, 3, 4}; 
std::vector<char> values = {'a', 'b', 'c', 'd', 'e', 'f'}; 

for(size_t n = 0; n < indices.size(); ++n) 
{ 
    while(indices[n] != n) 
    { 
     std::swap(values[n], values[indices[n]]); 
     std::swap(indices[n], indices[indices[n]]); 
    } 
}

編輯：

我想這應該是O（n）的，任何人不同意？

來源

2011-11-22 19:28:39 ronag

你可以對矢量排序，你的比較操作應該比較指數。當然，當移動數據時，您也必須移動索引。

最後，您的指數將只是0，1，...（n-1），數據將在相應的位置。

由於實現注意：您可以存儲的值，並在結構指數一起：

struct SortEntry 
{ 
    Data value; 
    size_t index; 
};

，並定義比較操作僅在指數看：

bool operator< (const SortEntry& lhs, const SortEntry& rhs) 
{ 
    return lhs.index < rhs.index; 
}

來源

2011-11-22 19:12:30 Vlad

有一個問題，比較運算符只給出值，而不是它們的索引 – Dani

但是然後我需要將數據複製到排序條目 – Dani

那麼，你有兩種方法：（1）使你的數據在適當的結構中一開始; （2）讓你的代碼只對索引進行排序，當將索引作爲排序過程的一部分移動時，也要移動適當的數據。 – Vlad

for(int i=0;i<=indexes.size();++i) 
for(int j=i+1;j<=indexes.size();++j) 
      if(indexes[i] > indexes[j]) 
         swap(indexes[i],indexes[j]), 
         swap(values[i],values[j]);

這是爲O （N 2）的複雜性，但應該適用於小數值。

你也能傳遞一個比較函數的C++ STL排序功能，如果你想O（N * logN）的

來源

2011-11-22 19:22:38 Cristy

由於您知道您的索引數組是[0, N)的置換，因此可以通過逐週期工作，以線性時間和就地（加上一個臨時）完成此操作。事情是這樣的：

size_t indices[N]; 
data_t values[N]; 

for (size_t pos = 0; pos < N; ++pos) // \ 
{          // } this loops _over_ cycles 
    if (indices[pos] == pos) continue; ///

    size_t i = pos; 
    const data_t tmp = values[pos]; 

    while (true)      // --> this loops _through_ one cycle 
    { 
    const size_t next = indices[i]; 
    indices[i] = i; 
    values[i] = values[next]; 

    if (next == pos) break; 
    i = next; 
    } 

    values[i] = tmp; 
}

這個實現的優點在每個時候，我們只需要使用一個臨時變量每循環一次使用swap。

如果數據類型是僅移動的，如果所有分配都被std::move()包圍，這仍然有效。

來源

2011-11-22 19:35:18

該解決方案運行在O（n）的時間：

int tmp; 
for(int i = 0; i < n; i++) 
    while(indexes[i] != i){ 
    swap(values[i], values[indexes[i]]); 
    tmp = indexes[i]; 
    swap(indexes[i], indexes[tmp]); 
    }

來源

2011-11-22 19:35:34

你能證明它的'O（n）'嗎？ – Dani

這將在O於ideone

int main(int argc, char *argv[]) 
{ 
int indexes[6]={2,3,5,1,0,4}; 
char values[6]={'a','b','c','d','e','f'}; 
int result[sizeof(indexes)/4];   //creating array of size indexes or values 
int a,i; 
for(i=0;i<(sizeof(indexes)/4);i++) 
{ 
    a=indexes[i];      //saving the index value at i of array indexes 
    result[a]=values[i];    //saving the result in result array 
} 
for (i=0;i<(sizeof(indexes)/4);i++) 
    printf("%c",result[i]);    //printing the result 
    system("PAUSE"); 
    return 0; 
}

來源

2011-11-23 06:57:46

按索引排列向量

回答

相關問題