2. Numeral System

Smeshan 89 Точки

2. Numeral System

Здравейте,

реших задача 2 от тук.

Ето решението: https://pastebin.com/kAuGFwjx

Доколкото разбирам, би следвало в момента да имам complexity O(N^2). Чудя се как мога да избегна двойния for цикъл и да намаля complexity :?
А и най-малкото ако имам повтаряш се символ, защо да го върти пак :?

Поздрави,
Илиян Павлов

Тагове:

07/05/2021 14:14:39 C++ Fundamentals

j.petrov_90 373 Точки

Привет,

Прав си, че решението ти е с квадратична сложност.

Опитай да прочетеш информация за lookup tables. Така ще успееш да свалиш сложността до линейна.

Когато решавахме задачата използвахме точно този подход.

Той много прилича на структури от данни, които ще изучаваме в C++Advanced, а именно std::map и std::unordered_map.

Поздрави

08/05/2021 17:46:31

Smeshan 89 Точки

Привет,
да, да, аз нещо се бях заблудил и търсих коя задача къде бяхме решавали по този начин, а то била самата тя.
Няма значение. Видях, пробвах и разбрах идеята. Прочетох за std::map и би било много лесно с тази структура :)
Поздрави,
Илиян Павлов

12/05/2021 10:57:00