sort in O(1) space complexity

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:22:23
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Leetcode BiWeekly Contest 144 — Solution Discussion

Shayan

До начала 19:52:23

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

Shayan

До начала 21:22:23

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
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	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя rahul_1234

sort in O(1) space complexity

Автор rahul_1234, история, 9 лет назад, По-английски

I want to sort the numbers using linked list in O(nlogn) time complexity and O(1) space complexity? Plz help me in this.

sort, linked list

rahul_1234
9 лет назад
7

Комментарии (6)

Показать архивные | Написать комментарий?

norpadon

9 лет назад, # |

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.

→ Ответить

rahul_1234

9 лет назад, # ^ |

← Rev. 2 →

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).

→ Ответить

yeputons

9 лет назад, # ^ |

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).

→ Ответить