Развернуть char[] на месте за O(n) и O(1) памяти
Реализуйте Reverse(s), разворачивающую char[] НА МЕСТЕ — изменяя тот же массив и ничего не возвращая. Требования: O(n) по времени и O(1) дополнительной памяти — без второго массива, без Array.Reverse, без LINQ. Массив из одного элемента или пустой должен остаться без изменений.
public static void Reverse(char[] s)
{
// ваш код здесь
}Допишите реализацию.
Два индекса l = 0 и r = s.Length - 1. Пока l < r, меняйте местами s[l] и s[r] (кортежный обмен (s[l], s[r]) = (s[r], s[l])), затем l++ и r--. Цикл кончается, когда они пересекаются, разворачивая на месте. O(n) по времени, O(1) дополнительной памяти.
- ✗Идти до самого конца и менять дважды, восстанавливая исходный порядок
- ✗Выделять второй массив, нарушая требование O(1) дополнительной памяти
- ✗Возвращать новое значение вместо изменения переданного массива на месте
- →Почему цикл должен останавливаться на
l < r, а не идти до конца? - →Как суррогатные пары (эмодзи) ломают наивный разворот по
char?
Задача
Развернуть массив символов на месте, не выделяя второй массив.
public static void Reverse(char[] s)
{
int l = 0, r = s.Length - 1;
while (l < r)
{
(s[l], s[r]) = (s[r], s[l]); // кортежный обмен на месте
l++;
r--;
}
}Как это работает
Два индекса начинают с краёв массива. На каждом шаге мы меняем местами зеркальную пару s[l] и s[r] кортежным обменом — он не требует временной переменной. Затем l двигается вправо, r — влево.
Ключевой момент — условие l < r: цикл останавливается, как только индексы встретятся или пересекутся. Если бы мы шли до конца, каждая пара была бы переставлена дважды и массив вернулся бы к исходному виду.
Каждая пара обменивается ровно один раз, поэтому сложность O(n) по времени и O(1) по памяти. Пустой массив или массив из одного элемента сразу не проходят условие l < r и остаются без изменений.
