use*_*683 5 algorithm data-structures
给定一个正整数序列和一个整数M,返回序列中第一个大于M的数字(如果不存在,则返回-1).
示例:sequence = [2,50,8,9,1],M = 3 - > return = 50
需要的每个查询的O(log n)(在预处理之后).
我已经想到了BST,但是考虑到一个提升序列,我会得到一个很长的路径,这不会给我O(logn)时间......
编辑:使用的结构也应该易于修改,即应该可以用给定的元素替换找到的元素并重复搜索另一个M(一切 - 除了预处理 - O(logn)).当然,如果我可以将"第一个更大"更改为"第一个更小"并且不必在算法中进行太多改变,那就太好了.如果它有帮助,我们可以假设所有数字都是正数而且没有重复.
ami*_*mit 10
创建第二个数组(让它成为aux)每个元素的位置i:( 原始数组中aux[i] = max { arr[0],arr[1], ... ,arr[i]}具有索引的所有元素的最大值j <= i).
很容易看出这个数组按性质排序,并且简单的二进制搜索aux将产生所需的索引.(如果元素不存在,使用二进制搜索很容易得到比请求元素大的第一个元素).
时间复杂度是O(n)预处理(仅执行一次)和O(logn)每个查询.