[NotABigFan]

Zadanie od Google:

Mając danych k posortowanych list jednokierunkowych, napisz funkcję, która scali je w jedną posortowaną listę jednokierunkową.

#dailycodingproblem #programowanie

[juszczus]

@NotABigFan: To jest Sortowanie przez scalanie tylko bez tego etapu w którym dzielimy ;)

[NotABigFan]

@juszczus: no dobra, to jest jedno z rozwiązań ale diabeł tkwi w szczegółach ( ͡° ͜ʖ ͡°)

[S.....s]

@NotABigFan jest tu jakiś haczyk? Czy da się szybciej niż logk * ilość elementów?

[NotABigFan]

@SuppressWarnings: da się w czasie O(n lg k) i pamięci O(1) jak się sprytnie merguje

[juszczus]

@SuppressWarnings: z intuicji wydaje mi się, że optymalnie ten case byłoby obskoczyć przy pomocy kopca list, w ten sposób, żeby na szczycie była lista z najmniejszą pierwszą liczbą (najmniejsza w ogóle). Po wyciągnięciu tej liczby, wyciągamy listę, która ją zawiera i wkładamy ją z powrotem na kopiec. Ale skrzywienie Pythonowe mówi mi, że koszt z takiego skomplikowania będzie zbyt duży jak na zysk, który uzyskamy z takiej optymalizacji ;)

[S.....s]

@NotABigFan e no to dość łatwe
@juszczus ja bym po prostu mergował po dwie, potem mergował dwie zmergowane, itd

[juszczus]

@SuppressWarnings: No czyli takie sortowanie przez scalanie tylko bez etapu dzielenia. Ale można też mergować wszystkie od razu jakby zrobić takie coś w stylu kolejki priorytetowej list, która pokazywałaby z której listy teraz wziąć kolejną najmniejszą.

[S.....s]

@SuppressWarnings chyba, chyba jednak ten mój sposób nie będzie dobry