adi*_*ijo 1 arrays algorithm data-structures
例如,考虑数组
A = [1,2,3,1,1,2,1,4,5,6,1,2,3]
数组中1索引之后的元素的第一次出现(出现的索引)2是3
数组中2索引之后第一次出现的元素2是5
数组中1索引之后第一次出现的元素4是6
如果在特定的索引之后没有出现,我们就可以输出 -1
我该如何有效地做到这一点？
如果是一次性查询,那么在该位置之后线性搜索数组不能做得更好:O(n).
如果需要多次在同一个数组上执行类似的查询,请从每个不同的元素构建一个哈希多图,以及它所在的索引的排序列表.然后它只是一个问题:a)查找元素的排序列表b)二进制搜索排序列表(匹配不需要精确),然后返回大于指定位置的后继元素/第一个元素.我确定你可以处理-1应该归还的案件.这是O(1)+ O(logn)= O(logn).