I want to sort the numbers using linked list in O(nlogn) time complexity and O(1) space complexity? Plz help me in this.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.11.2024 11:20:28 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Use merge sort: If your list is empty or contains single element, it is already sorted, otherwise split it into two equal parts, sort them recursively and merge into single sorted list.
Yes, but how to maintain O(1) space complexity, thats the only issue I am facing. Can you plz provide me link where I can find code or explanation of how to maintain O(1) space complexity( meeting O(nlogn) time complexity).
Do you have a linked list or array? The former allows you to re-arrange, insert and remove elements arbitrary in O(1), the latter does not (but it also does not require keeping a pointer to element to make any action).
Simple implementation. https://gist.github.com/Norpadon/410649f0389749601980
This is recursive so has O(logn) space complexity
Thanks, i missed that.
Here is non-recursive version: https://gist.github.com/Norpadon/e5a9f1b1139a17a9500e
Code is a bit messy, but idea should be clear.