给定一个段落,其中一行中所有单词的长度具有以下属性:
- 奇数位置词按其长度的递增顺序排列。
- 偶数位置词按其长度的递减顺序排列。
给你一个词,你必须编写一段代码来在给定的段落中搜索它并返回行号。
最佳答案
如果每一行由一个单词列表给出,它实际上是两个排序的子列表:
(1) 奇词列表:按长度递增排序
(2) 偶数列表:按长度递减排序
在两个列表上使用二进制搜索,比较器符合:word.length()
一旦找到匹配[您要查找的词和您当前正在搜索的列表中的词]长度相同:检查它是否是同一个词。
对每一行重复。
复杂度 [对于每一行]:O(logn * |S|)
其中 |S|
是你的字的大小和n
是一行中的单词数。
关于algorithm - 在给定段落中搜索单词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9181731/