Автор: Sergey Teplyakov

Есть ряд способов сдвинуть массив влево на N элементов. Можно взять и сделать N сдвигов по одному элементу, получив квадратичную сложность. Можно создать целевой массив по размеру исходного и вычислить положение каждого элемента после сдвига. Хорошо, но скорость линейна, затраты по памяти - тоже.
Если чутка подумать, то можно придумать реализацию, которая мутирует массив и дает линейную скорость и константные затраты по памяти. Но есть один очень элегантный способ из 3-х строк на основе чудо Span of T из System.Memory:
public static void RotateLeft(int[] input, int direction) { input.AsSpan(0, direction).Reverse(), input.AsSpan(direction).Reverse(), input.AsSpan().Reverse(), } Идея такая: чтобы сдвинуть массив из K элементов на N элементов влево, нужно перевернуть первые N элементов в массиве, затем последние K - N -1 элементов, а затем перевернуть весь массив:
// direction == 2, input.Length == 7 input.AsSpan(0, direction).Reverse(), // [2][1][3][4][5][6][7] input.AsSpan(direction).Reverse(), // [2][1][7][6][5][4][3] input.AsSpan().Reverse(),// [3][4][5][6][7][1][2]
Получается два прохода по массиву, но зато с читабельностью решения все очень ОК.
Помогла статья? Оцените её!
0 из 5. Общее количество голосов - 0
 

You have no rights to post comments

Дмитрий Крикунов

Публикую статьи, обучающие курсы и новости по программированию: алгоритмам, языкам (С++, Java), параллельному программированию, паттернам и библиотекам (Qt, boost).