Dwa wskaźniki

Scalanie dwóch uporządkowanych ciągów - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Dwie listy **uporządkowane** łączy się w jedną uporządkowaną bez sortowania od nowa: wskaźniki `i` i `j` pokazują pierwsze niewzięte elementy obu list. W każdym kroku mniejszy z nich trafia do wyniku, a jego wskaźnik przesuwa się dalej. Gdy jedna lista się skończy, resztę drugiej dopisuje się w całości. Każdy element jest brany raz, więc scalanie ma złożoność liniową: co najwyżej `len(a) + len(b) - 1` porównań.

def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result += a[i:]
    result += b[j:]
    return result

print(merge([1, 4, 7, 10], [2, 3, 8, 12, 15]))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 2, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.