Link do zadania Leetcode: 88. Merge Sorted Array. Odwiedź link, aby zapoznać się z treścią zadania.

Tłumaczenie treści

Dostajemy dwie tablice typu int posortowane w niemalejącym porządku: nums1 i nums2. Do tego dwie zmienne typu int, n i m, które równe są odpowiednio ilości elementów do złączenia w nums1 oraz ilości elementów do złączenia w nums2. No i właśnie, naszym zadaniem jest utworzyć z nums1 i nums2 jedną tablicę, która również będzie posortowana w kolejności niemalejącej.

Haczykiem jest to, że nie możemy zwrócić w funkcji nowej tablicy. Zamiast tego musimy przekształcić nums1 tak, aby stanowiła końcową, połączoną tablicę. Aby to było możliwe tablica nums1 ma wielkość m + n. Na początku tablicy mamy m elementów, które musimy zawrzeć w końcowej tablicy, a następnie n zer.

Powiedzmy sobie może dlaczego w zadaniu pojawia się stwierdzenie „w kolejności niemalejącej” (non-decreasing order), zamiast „w kolejności rosnącej” (increasing order). Kolejność niemalejąca pozwala nam na powtarzające się elementy. Tzn. niemalejąca jest tablica: [1, 2, 2, 3, 3, 3, 4, 5], ale nie jest już ona rosnąca, ponieważ nie każdy kolejny element jest większy od poprzedniego. Czyli każda rosnąca jest niemalejącą, ale nie każda niemalejąca jest rosnącą.

Rozwiązanie

Pomocny w rozwiązaniu zadania jest fakt, że tablice są posortowane. Musimy więc iterować po tablicach i porównywać ich elementy. Gdybyśmy tworzyli nową tablicę, zapewne zaczęlibyśmy porównywać elementy od początku tablic. Ale wolne miejsce na końcu nums1, wymusza uzupełnianie jej od końca, a więc od największych elementów. Gdybyśmy uzupełniali tablicę od początku, stracilibyśmy elementy tablicy nums1. Dlatego porównujemy ostatnie elementy tablic. Musimy również śledzić ostatni wolną pozycję w nums1 za pomocą zmiennej, np. 'index’.

Element, który okazuje się większy dodajemy do nums1 w pozycji index. Następnie zmniejszamy m, jeśli dodaliśmy element z nums1 lub zmniejszamy n, jeśli był to element z nums2. Ostatnią czynnością w pętli jest zmniejszenie zmiennej index o 1.

Ostatni krok to pętla while, która dodaje pozostałe elementy nums1, jeśli oczywiście takie istnieją:

I to wszystko. Tak jak było powiedziane w treści zadania i jak nakazuje nam void w sygnaturze funkcji, niczego nie zwracamy. Ostateczne rozwiązanie prezentuje się tak:

Jeżeli chodzi o analizę wydajności naszego rozwiązania, to będzie to O(m + n), ponieważ w najgorszym przypadku (gdyby każdy element nums1 okazywał się większy od elementu nums2), będziemy musieli przeiterować po każdym elemencie z obu tablic.

Daj znać w komentarzu czy podoba Ci się taka forma wpisu. Może mógłbym coś poprawić, a może zauważyłeś błąd? Daj mi znać i pozwól na jak najszybsze wprowadzenie poprawki 🙂

Source of m&m’s picture: Mary Kreul https://www.flickr.com/photos/4krichards/31712357957