В тази статия ще разгледаме как да решим проблема със сливането на два сортирани списъка в 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
, който е сортираният списък, съдържащ всички елементи от двата входни списъка.
Ето стъпките за алгоритъма:
- Инициализирайте броячи
i
,j
иk
на 0. - Създайте нов празен списък
mergedList
. - Преминете през двата входни списъка, докато
i
иj
са по-малки от съответните им дължини на списъка. - Сравнете текущите стойности на двата списъка.
- Добавете по-малката стойност към
mergedList
. - Увеличете съответния брояч
i
,j
илиk
. - Преминете през останалите елементи в непразния списък и ги добавете към
mergedList
. - Връщане
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.