给定一个正整数序列和一个整数M,返回序列中第一个大于M的数字(如果不存在,则返回-1).
示例:sequence = [2,50,8,9,1],M = 3 - > return = 50
需要的每个查询的O(log n)(在预处理之后).
我已经想到了BST,但是考虑到一个提升序列,我会得到一个很长的路径,这不会给我O(logn)时间......
编辑:使用的结构也应该易于修改,即应该可以用给定的元素替换找到的元素并重复搜索另一个M(一切 - 除了预处理 - O(logn)).当然,如果我可以将"第一个更大"更改为"第一个更小"并且不必在算法中进行太多改变,那就太好了.如果它有帮助,我们可以假设所有数字都是正数而且没有重复.