Question

我有两个矢量:病媒和指数病媒。我如何使病媒由指数媒介来安排? 和:

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

The indexes vector will always contain the range [0, n) and each index only once.
I need this operation to be done in place because the code is going to be run on a device with low memory.
How can I do this in c++? I can use c++11

Answer 1

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]]);
    }
}

EDIT:

我认为这应该是O(n),任何人都不同意吗?

Answer 2

由于你知道,你的指数阵列是<代码>[0,N]的变动,你可以按工作周期在班时间和地点(+one<>>>/em>,临时)进行折算。与此类似:

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(<>>/code>进行四舍五入,则仍有效。

Answer 3

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(N2)的复杂性,但应当对少数数值进行细微的工作。

You can also pass a comparison function to the C++ STL sort function if you want O(N*logN)

Answer 4

您的对比工作应该对指数进行比较。当然,在把数据上调时,你也必须改变指数。

最后,你的指数将仅为0、1、......(n-1),数据将相应地点。

As implementation note: you can store the values and indices together in a structure:

struct SortEntry
{
    Data value;
    size_t index;
};

并界定比较操作者只研究指数:

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

Answer 5

This solution runs in O(n) time:

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]);
  }

Answer 6

This will run in O(n) time without any error.Check it on 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;
}

友情链接