PrepBro
← Назад к вопросам

Слияние двух отсортированных массивов

2.0 Middle🔥 121 комментариев
#Стандарты разработки

Условие

Есть два массива Y[y] и Z[z], упорядоченные по убыванию. Напишите код, который проходит по ним в одном цикле длиной (y+z) и выводит значения в порядке возрастания.

Важно: использовать только один цикл, не использовать встроенную сортировку.

Пример

Вход:

  • Y = [9, 7, 3, 1]
  • Z = [8, 5, 2]

Выход: [1, 2, 3, 5, 7, 8, 9]

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Обзор задачи

Эта задача требует слияния двух отсортированных массивов в один упорядоченный результат с оптимизацией — за один цикл длиной (y+z). Это классическая задача из алгоритма Merge Sort и демонстрирует понимание двух указателей (two pointers), логики слияния и оптимизации циклов.

Особенность: входные массивы отсортированы по убыванию, а результат должен быть по возрастанию. Это требует инверсии логики сравнения.

Математическая логика

Для слияния двух отсортированных массивов:

  1. Используем два указателя: один на конец Y, другой на конец Z
  2. На каждой итерации сравниваем текущие элементы
  3. Берём меньший элемент (так как нам нужно возрастание из убывающих)
  4. Помещаем в результирующий массив
  5. Сдвигаем соответствующий указатель

Реализация 1: Базовый вариант с двумя указателями

Процедура СлитьДваМассиваОптимизированно(Y, Z, Результат)
    ДлинаY = Y.Количество();
    ДлинаZ = Z.Количество();
    ОбщаяДлина = ДлинаY + ДлинаZ;
    
    УказательY = ДлинаY - 1; // Начинаем с конца Y
    УказательZ = ДлинаZ - 1; // Начинаем с конца Z
    
    // Единственный цикл длины (y+z)
    Для ПозицияРезультата = 0 По ОбщаяДлина - 1 Цикл
        
        // Если в Y остались элементы
        Если УказательY >= 0 И УказательZ >= 0 Тогда
            // Сравниваем текущие элементы обоих массивов
            Если Y[УказательY] <= Z[УказательZ] Тогда
                // Y[УказательY] меньше или равен — берём его
                Результат[ПозицияРезультата] = Y[УказательY];
                УказательY = УказательY - 1;
            Иначе
                // Z[УказательZ] больше — берём его
                Результат[ПозицияРезультата] = Z[УказательZ];
                УказательZ = УказательZ - 1;
            КонецЕсли;
            
        // Если в Y закончились элементы
        ИначеЕсли УказательY < 0 Тогда
            Результат[ПозицияРезультата] = Z[УказательZ];
            УказательZ = УказательZ - 1;
            
        // Если в Z закончились элементы
        Иначе
            Результат[ПозицияРезультата] = Y[УказательY];
            УказательY = УказательY - 1;
        КонецЕсли;
        
    КонецЦикла;
КонецПроцедуры

Реализация 2: С инициализацией результирующего массива

Функция СлитьДваМассиваСРезультатом(Y, Z)
    ДлинаY = Y.Количество();
    ДлинаZ = Z.Количество();
    ОбщаяДлина = ДлинаY + ДлинаZ;
    
    Результат = Новый Массив(ОбщаяДлина);
    
    УказательY = ДлинаY - 1;
    УказательZ = ДлинаZ - 1;
    
    Для ПозицияРезультата = 0 По ОбщаяДлина - 1 Цикл
        
        Если УказательY >= 0 И УказательZ >= 0 Тогда
            
            Если Y[УказательY] <= Z[УказательZ] Тогда
                Результат[ПозицияРезультата] = Y[УказательY];
                УказательY = УказательY - 1;
            Иначе
                Результат[ПозицияРезультата] = Z[УказательZ];
                УказательZ = УказательZ - 1;
            КонецЕсли;
            
        ИначеЕсли УказательY < 0 Тогда
            Результат[ПозицияРезультата] = Z[УказательZ];
            УказательZ = УказательZ - 1;
        Иначе
            Результат[ПозицияРезультата] = Y[УказательY];
            УказательY = УказательY - 1;
        КонецЕсли;
        
    КонецЦикла;
    
    Возврат Результат;
КонецФункции

Реализация 3: С использованием Добавить вместо индексации

Функция СлитьДваМассиваДобавлением(Y, Z)
    ДлинаY = Y.Количество();
    ДлинаZ = Z.Количество();
    ОбщаяДлина = ДлинаY + ДлинаZ;
    
    Результат = Новый Массив();
    
    УказательY = ДлинаY - 1;
    УказательZ = ДлинаZ - 1;
    
    // Цикл выполняется (y+z) раз
    Для СчётчикИтераций = 0 По ОбщаяДлина - 1 Цикл
        
        Если УказательY >= 0 И УказательZ >= 0 Тогда
            
            Если Y[УказательY] <= Z[УказательZ] Тогда
                Результат.Добавить(Y[УказательY]);
                УказательY = УказательY - 1;
            Иначе
                Результат.Добавить(Z[УказательZ]);
                УказательZ = УказательZ - 1;
            КонецЕсли;
            
        ИначеЕсли УказательY < 0 Тогда
            Результат.Добавить(Z[УказательZ]);
            УказательZ = УказательZ - 1;
        Иначе
            Результат.Добавить(Y[УказательY]);
            УказательY = УказательY - 1;
        КонецЕсли;
        
    КонецЦикла;
    
    Возврат Результат;
КонецФункции

Реализация 4: С обработкой особых случаев

Функция СлитьДваМассиваОстрожно(Y, Z)
    // Обработка пустых массивов
    Если Y.Количество() = 0 Тогда
        Возврат Z;
    КонецЕсли;
    
    Если Z.Количество() = 0 Тогда
        Возврат Y;
    КонецЕсли;
    
    ДлинаY = Y.Количество();
    ДлинаZ = Z.Количество();
    ОбщаяДлина = ДлинаY + ДлинаZ;
    
    Результат = Новый Массив(ОбщаяДлина);
    
    УказательY = ДлинаY - 1;
    УказательZ = ДлинаZ - 1;
    
    Для ПозицияРезультата = 0 По ОбщаяДлина - 1 Цикл
        
        // Если оба указателя в допустимом диапазоне
        Если УказательY >= 0 И УказательZ >= 0 Тогда
            
            Если Y[УказательY] <= Z[УказательZ] Тогда
                Результат[ПозицияРезультата] = Y[УказательY];
                УказательY = УказательY - 1;
            Иначе
                Результат[ПозицияРезультата] = Z[УказательZ];
                УказательZ = УказательZ - 1;
            КонецЕсли;
            
        // Если в Y нет элементов — берём из Z
        ИначеЕсли УказательY < 0 Тогда
            Если УказательZ >= 0 Тогда
                Результат[ПозицияРезультата] = Z[УказательZ];
                УказательZ = УказательZ - 1;
            КонецЕсли;
            
        // Если в Z нет элементов — берём из Y
        Иначе
            Если УказательY >= 0 Тогда
                Результат[ПозицияРезультата] = Y[УказательY];
                УказательY = УказательY - 1;
            КонецЕсли;
        КонецЕсли;
        
    КонецЦикла;
    
    Возврат Результат;
КонецФункции

Реализация 5: Усложнённый вариант с доп. логикой

Функция СлитьДваМассиваСМедианой(Y, Z)
    ДлинаY = Y.Количество();
    ДлинаZ = Z.Количество();
    ОбщаяДлина = ДлинаY + ДлинаZ;
    
    Результат = Новый Массив();
    МедианаПозиция = ОбщаяДлина / 2;
    
    УказательY = ДлинаY - 1;
    УказательZ = ДлинаZ - 1;
    
    Для СчётчикИтераций = 0 По ОбщаяДлина - 1 Цикл
        
        Текущий = Неопределено;
        
        Если УказательY >= 0 И УказательZ >= 0 Тогда
            Если Y[УказательY] <= Z[УказательZ] Тогда
                Текущий = Y[УказательY];
                УказательY = УказательY - 1;
            Иначе
                Текущий = Z[УказательZ];
                УказательZ = УказательZ - 1;
            КонецЕсли;
        ИначеЕсли УказательY < 0 Тогда
            Текущий = Z[УказательZ];
            УказательZ = УказательZ - 1;
        Иначе
            Текущий = Y[УказательY];
            УказательY = УказательY - 1;
        КонецЕсли;
        
        Результат.Добавить(Текущий);
    КонецЦикла;
    
    Возврат Результат;
КонецФункции

Примеры использования

// Пример 1: базовое использование
Y = Новый Массив();
Y.Добавить(9);
Y.Добавить(7);
Y.Добавить(3);
Y.Добавить(1);

Z = Новый Массив();
Z.Добавить(8);
Z.Добавить(5);
Z.Добавить(2);

Результат = СлитьДваМассиваСРезультатом(Y, Z);
// Ожидаемо: [1, 2, 3, 5, 7, 8, 9]

ДляКаждого Элемент Из Результат Цикл
    Сообщить(Элемент); // Выводит в порядке возрастания
КонецЦикла;

// Пример 2: пустые массивы
ПустойY = Новый Массив();
ПустойZ = Новый Массив();
ПустойZ.Добавить(3);

Результат2 = СлитьДваМассиваОстрожно(ПустойY, ПустойZ);
// Ожидаемо: [3]

// Пример 3: один элемент в каждом
ОдинY = Новый Массив();
ОдинY.Добавить(5);

ОдинZ = Новый Массив();
ОдинZ.Добавить(3);

Результат3 = СлитьДваМассиваСРезультатом(ОдинY, ОдинZ);
// Ожидаемо: [3, 5]

Анализ алгоритма

Временная сложность: O(n+m), где n и m — размеры Y и Z. Каждый элемент посещается ровно один раз.

Пространственная сложность: O(n+m) для результирующего массива.

Количество итераций: Ровно (y+z), как требуется в условии.

Ключевые моменты

  1. Два указателя — начинаем с конца обоих массивов
  2. Убывание в возрастание — инвертируем логику сравнения
  3. Один цикл — ровно (y+z) итераций
  4. Граничные случаи — обработка пустых массивов и остатков
Слияние двух отсортированных массивов | PrepBro