В тази статия ще разгледаме как да решим проблема със сливането на два сортирани списъка в JavaScript. Този проблем изисква да обединим два сортирани списъка в нов сортиран списък.

Входът за този проблем се състои от два сортирани списъка, а изходът е нов списък, който съдържа всички елементи от двата входни списъка в сортиран ред. Ще разгледаме как да решим този проблем с помощта на JavaScript и ще разберем алгоритъма зад него.

Постановка на проблема и изисквания

Проблемът със сливането на два сортирани списъка изисква да вземем два сортирани масива като вход и да ги обединим в един сортиран масив. Входните масиви могат да бъдат с произволен размер и могат или не могат да бъдат с еднакъв размер. Резултатът трябва да бъде нов масив, който съдържа всички елементи от входните масиви в сортиран ред.

Например, ако входните масиви са [1, 3, 4] и [2, 5, 6], изходът трябва да бъде [1, 2, 3, 4, 5, 6].

Подход и алгоритъм

Проблемът със сливането на два сортирани списъка може да бъде решен с помощта на прост алгоритъм. Можем да започнем с инициализиране на три брояча i, j и k до 0. Създаваме също нов празен списък, наречен mergedList.

След това преминаваме през двата входни списъка, докато броячите i и j са по-малки от дължината на съответните им списъци. Във всяка итерация сравняваме текущите стойности на двата списъка. След това добавяме по-малката стойност към mergedList. След това увеличаваме съответния брояч i, j или k.

След като стигнем до края на един от списъците с входни данни, преминаваме през останалите елементи в непразния списък и ги добавяме към mergedList.

Накрая връщаме mergedList, който е сортираният списък, съдържащ всички елементи от двата входни списъка.

Ето стъпките за алгоритъма:

  1. Инициализирайте броячи i, j и k на 0.
  2. Създайте нов празен списък mergedList.
  3. Преминете през двата входни списъка, докато i и j са по-малки от съответните им дължини на списъка.
  4. Сравнете текущите стойности на двата списъка.
  5. Добавете по-малката стойност към mergedList.
  6. Увеличете съответния брояч i, j или k.
  7. Преминете през останалите елементи в непразния списък и ги добавете към mergedList.
  8. Връщане mergedList.

Код Обяснение

Нека да разгледаме кода на JavaScript за проблема с обединяването на два сортирани списъка и да преминем през всеки ред.

function mergeTwoLists(list1, list2) {
  let i = 0, j = 0, k = 0;
  const mergedList = [];

  while (i < list1.length && j < list2.length) {
    if (list1[i] <= list2[j]) {
      mergedList[k] = list1[i];
      i++;
    } else {
      mergedList[k] = list2[j];
      j++;
    }
    k++;
  }

  while (i < list1.length) {
    mergedList[k] = list1[i];
    i++;
    k++;
  }

  while (j < list2.length) {
    mergedList[k] = list2[j];
    j++;
    k++;
  }

  return mergedList;
}

Функцията mergeTwoLists взема два входни списъка list1 и list2 и връща нов сортиран списък.

Функцията инициализира три брояча i, j и k на 0. Тя също така създава празен масив mergedList.

Първият цикъл while сравнява текущите стойности на двата входни списъка, докато броячите i и j са по-малки от дължините на съответните им списъци. След това по-малката стойност се добавя към mergedList. След това съответният брояч i, j или k се увеличава.

Следващите два цикъла while обработват останалите елементи в непразния списък. След това останалите елементи се добавят към mergedList.

Накрая функцията връща mergedList.

Ето няколко примера за JavaScript код за проблема с обединяването на два сортирани списъка в действие:

Примери

Нека да разгледаме някои примери за проблема с обединяването на два сортирани списъка в действие.

Пример 1

const list1 = [1, 2, 4];
const list2 = [1, 3, 4];

console.log(mergeTwoLists(list1, list2));
// Output: [1, 1, 2, 3, 4, 4]

В този пример имаме два сортирани списъка [1, 2, 4] и [1, 3, 4]. Функцията mergeTwoLists се извиква с тези два списъка като вход. Резултатът е нов списък, който съдържа всички елементи от двата входни списъка в сортиран ред, който е [1, 1, 2, 3, 4, 4].

Пример 2

const list3 = [];
const list4 = [0];
console.log(mergeTwoLists(list3, list4));
// Output: [0]

В този пример имаме празен списък list3 и сортиран списък [0]. Функцията mergeTwoLists се извиква с тези два списъка като вход. Резултатът е нов списък, който съдържа всички елементи от двата входни списъка в сортиран ред, който е [0].

Заключение

В тази статия обсъдихме проблема със сливането на два сортирани списъка и как да го решим с помощта на JavaScript. Също така разгледахме подхода и алгоритъма за обединяване на два сортирани списъка и преминахме през кода на JavaScript стъпка по стъпка.

Проблемът със сливането на два сортирани списъка е основен проблем в компютърните науки и е отлично упражнение за подобряване на вашите умения за решаване на проблеми. Надявам се, че тази статия ви е помогнала да разберете проблема и как да го разрешите с помощта на JavaScript.