вращение массива против часовой стрелки, проблемы времени выполнения - PullRequest
Новая
       21

вращение массива против часовой стрелки, проблемы времени выполнения

2 голосов
/ 07 февраля 2020

В вопросе мне пришлось повернуть данные в массиве против часовой стрелки на d чисел. Но для запуска требуется больше времени, чем требуется для квалификации. Может кто-нибудь помочь мне с тем, как оптимизировать код, чтобы запустить его за меньшее время? Спасибо!

вот код: 

int main() {
int test_cases,size,d;
std::cin>>test_cases;
while(test_cases!=0){
std::cin>>size>>d;
int ar[size];
for(int i=0;i<size;i++){
    std::cin>>ar[i];
}
while(d!=0){
    int x = ar[0];
    for(int i=1;i<size;i++){
        ar[i-1]=ar[i];
    }
    ar[size-1]=x;
    d--;
}
for(int i=0;i<size;i++){
    std::cout<<ar[i]<<" ";
}
test_cases--;
cout<<endl;
}}

Ответы [ 3 ]

2 голосов
/ 07 февраля 2020

Вы должны переместить каждый элемент один раз, как это предлагается в комментариях. Выяснить алгоритм для этого не так сложно. Однако зачем изобретать велосипед?

Вы можете просто использовать std::rotate. Я буду считать, против часовой стрелки означает влево , а массив начинается слева и заканчивается справа:). 

std::vector<int> v {1,2,3};
size_t dist = 4; // rotate 4 to the left
std::rotate(v.begin(), v.begin() + dist % v.size(), v.end());

Если вы действительно настаиваю на том, чтобы заново изобрести колесо, я думаю, есть много возможных алгоритмов Приведенный ниже пример начинается с индекса idx = 0 и сохраняет там значение с индексом idx_moved = idx + dist, где dist - это расстояние вращения. Затем мы делаем то же самое с idx = idx_moved и повторяем это N раз, где N - размер массива. Я использовал std::vector здесь, но это не меняет алгоритм. 

std::vector<int> v {1,2,3,4,5};
size_t dist = 3; // distance to move to the left

size_t idx = 0;
int tmp = v[0]; // store the initial value

for (size_t it = 0; it < v.size(); ++it)
{
    size_t idx_moved = (idx + dist) % v.size();
    v[idx] = v[idx_moved];
    idx = idx_moved;
}
v[dist * (v.size() -1 ) % v.size()] = tmp; // store the initial value back
1 голос
/ 07 февраля 2020

Хотя проблема заключается в повороте влево (как вы говорите против часовой стрелки), мы всегда можем переформулировать его как поворот на заданное (положительное) смещение вправо.

Например, учитывая следующий массив (который должен быть std::vector, в C ++) размера n = 9 

1 2 3 4 5 6 7 8 9

Поворот влево от 3 мест ( d *) 1010 * = 3, в задаче ОП), эквивалентен повороту справа от 6 мест (назовем это смещение k , так что k = 6): 

4 5 6 7 8 9 1 2 3

Если вы можете использовать дополнительную память, самый простой способ - скопировать первые n - k элементов (или последние k элементов) во временный буфер, переместите остальные k в начале (или первые n - k в конце), а затем скопируйте элементы из буфера обратно в последние позиции (или, вы знаете, ..). 

    [1 2 3 4 5 6 7 8 9]      [     ]
     ^ ^ ^                               Copy the first elements
    [1 2 3 4 5 6 7 8 9]      [1 2 3]
           ^ ^ ^ ^ ^ ^                   Move to the beginning
    [4 5 6 7 8 9 7 8 9]      [1 2 3]
                              ^ ^ ^      Copy back
    [4 5 6 7 8 9 1 2 3]      [1 2 3]

Если вы не можете это сделать, и для назначения требуется изменить массив на месте, хорошая альтернатива алгоритму жонглирования Орифим, показанный в других ответах, требует только трех обратных: 

    [1 2 3 4 5 6 7 8 9]
     ^ ^ ^                     Reverse the first n - k elements     
    [3 2 1 4 5 6 7 8 9]
           ^ ^ ^ ^ ^ ^         Reverse the last k elements  
    [3 2 1 9 8 7 6 5 4]
     ^ ^ ^ ^ ^ ^ ^ ^ ^         Reverse all
    [4 5 6 7 8 9 1 2 3]

Если вы пишете реальный код, вам лучше использовать std :: rotate .

1 голос
/ 07 февраля 2020

Чтобы сделать это быстрее, вы можете использовать A Juggling Algorithm, здесь хорошо объяснил, как это работает. Основной принцип заключается в том, что вы перемещаете элементы не один за другим, а перемещаете элементы в равных наборах.

...