Есть ряд способов сдвинуть массив влево на N элементов. Можно взять и сделать N сдвигов по одному элементу, получив квадратичную сложность. Можно создать целевой массив по размеру исходного и вычислить положение каждого элемента после сдвига. Хорошо, но скорость линейна, затраты по памяти - тоже.
Если чутка подумать, то можно придумать реализацию, которая мутирует массив и дает линейную скорость и константные затраты по памяти. Но есть один очень элегантный способ – из 3-х строк на основе чудо Span of T из System.Memory:
Получается два прохода по массиву, но зато с читабельностью решения все очень ОК.
Если чутка подумать, то можно придумать реализацию, которая мутирует массив и дает линейную скорость и константные затраты по памяти. Но есть один очень элегантный способ – из 3-х строк на основе чудо Span of T
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]
Получается два прохода по массиву, но зато с читабельностью решения все очень ОК.
Справедливости ради, хочу отметить, что это циклический сдвиг влево.
ОтветитьУдалитьНе совсем понял мысль. Да, это одна из реализаций циклического сдвига влево. Просто, ИМХО, одна из самых кратких и выразительных.
Удалитьnit: Мне показалось, что Vasya всего лишь хотел справедливо заметить, что слово "сдвиг" в заголовке и теле поста лучше бы заменить на "циклический сдвиг".
УдалитьВ своё время этот фокус произвёл на меня большое впечатление... минут 20 рисовал на листике пытаясь понять как этот трюк работает :)
ОтветитьУдалитьОн же, но чуть с большим wow-эффектом (IMHO) используется в задачке Reverse Words: когда необходимое переставить слова в предложении в обратном порядке. Например: "Michael Jordan" => "Jordan Michael". Необходимо сделать "реверс" каждого слова и потом реверс всей строки целиком, что в конечном итоге даёт практически линейную сложность.
О! Отличный трюк.
УдалитьЗ.Ы. Сложность-то линейная, просто коэффициент равен 2.
Фокус интересный. Но по поводу читабельности - не соглашусь. Оно же крайне не очевидно. Но элегантный, да
ОтветитьУдалитьНу такое... по этой теории каждый второй алгоритм можно зафукать :)))
УдалитьТак гораздо понятнее, чем циклический сдвиг врукопашную.
Удалитьhttp://codelib.ru/task/cycle_shift/
Мне кажется, что без комментария с небольшим примером решение неочевидно. Но оно читаемо, поскольку состоит из 3 строк. После же того, как прогнан в голове/дебагере один пример, то решение садится в голове прочно.
УдалитьПочему "затем последние K - N -1 элементов", если необходимо перевернуть K - N последних элементов?
ОтветитьУдалитьOff-by-one error:)
УдалитьВ "Жемчужинах программирования" читал что-то подобное... я уже не помню, но там с помощью реверса решалась задача. Интуитивно восстановил алгоритм: Сложность 4N, дополнительной памяти не требуется.
ОтветитьУдалитьПример:
исходный массив: 1234567 сдвиг вправо на 3
преобразования:
1234765
4321765
5671234
5674321
Этот комментарий был удален автором.
УдалитьЭтот комментарий был удален автором.
УдалитьЭтот комментарий был удален автором.
УдалитьСложность 2N
ОтветитьУдалитьГлавное, чтобы подобные алгоритмы оставались уделом олимпиад и научных статей. В промышленном коде применять такое боже упаси. Понадобится после аффтора что-то поправить в задаче, голову сломаешь и времени убьешь черт знает сколько.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьКак-то все очень сложно. Вот сдвиг массива влево на Go Lang: append(a[int(d):], a[0:int(d)]...)
ОтветитьУдалитьКак уже отметили выше, это действительно предложено в "Programming Pearls".
ОтветитьУдалитьКогда-то на собеседовении решил эту задачку таким образом:
ОтветитьУдалитьpublic int[] LeftRotation(int[] arr, int d)
{
var newArr = new int[d];
Array.Copy(arr, newArr, d);
Array.Copy(arr, d, arr, 0, arr.Length - d);
Array.Copy(newArr, 0, arr, arr.Length - d, newArr.Length);
return arr;
}
Когда писал конечный автомат на си для микроконтроллера, то приходилось с этим сталкиваться. Жаль, что на си для arm нет такой фичи.
ОтветитьУдалитьЯ видел комментарии людей, которые уже получили ссуду от г-на Бенджамина Ли, и я решил подать заявку в соответствии с их рекомендациями, и всего через 5 дней я подтвердил свою ссуду на моем банковском счете на общую сумму 850 000,00 долларов США, которую я запросил. Это действительно отличная новость, и я советую всем, кому нужен настоящий кредитор, подать заявку по электронной почте: 247officedept@gmail.com или WhatsApp: + 1-989-394-3740. Я счастлив, что получил ссуду, о которой просил.
ОтветитьУдалитьPretty nice post. I just stumbled upon your weblog and wished to say that I have truly enjoyed surfing around your blog posts. 토토
ОтветитьУдалить