Вы данный абзац, в котором длина всех слов в строке, имеет следующие свойства:Поиск слова в данном пункте
Вам дается слово, и вам необходимо написать код для его поиска в данном параграфе и вернуть номер строки.
Если каждая строка задается список слов, это на самом деле два отсортированных подсписки:
(1) Список нечетных слов: упорядоченные increasinly по длине
(2) список четных слов: сортированы убывая по длине
Используйте двоичный поиск на обоих списках, с компаратором Accordding к: word.length()
После того, как вы нашли матч [слово, которое вы ищете, и слово в списке, вы в настоящее время ищете] находится в том же length: проверьте, является ли это одним и тем же словом.
повтор для каждой линии.
Сложность [для каждой строки]: O(logn * |S|) где |S| это размер вашего слова и n этого количества слов в строке.
Кажется, нет требований к сложности набора времени - так почему бы просто не реализовать линейный поиск? Возможно, это странное/даже просто добавленное, чтобы смутить вас! Держите его простым;)
В вопросе интервью ответ *** никогда *** «линейный поиск». –
Интервью У Qs может быть некоторый шум, чтобы смутить вас. Ваша работа заключается в том, чтобы извлечь соответствующие фрагменты. –
В моем ответе я не пытался быть грубым. Я просто перечитываю Q, прежде чем переходить на сложное решение! Но, конечно, я тоже признаю это решение! Cheers :) –
пахнет домашней работой –
Как указывается данный параграф? как 'char []'/'String' или как список слов/строк? [и каждое слово/строка - 'char' /' String'] – amit
@mekici Недавно было задано в интервью. – d123