Професионална програма
Loading...
+ Нов въпрос
Smeshan avatar Smeshan 73 Точки

2. Numeral System

Здравейте,

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

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

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

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

Тагове:
1
C++ Fundamentals
j.petrov_90 avatar j.petrov_90 327 Точки

Привет,

 

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

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

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

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

Поздрави

0
Smeshan avatar Smeshan 73 Точки

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

0