数组指定索引对应上一个5、下一个6的索引查找优化方案咨询
静态数组查询最优方案分析
你提到的两种实现已经是静态数组场景下的最优方案,二者时间复杂度下限一致,仅适用场景不同,没有效率更高的通用实现:
两种方案的适用场景对比
- 前缀/后缀预处理数组方案
预处理时间复杂度O(n),空间复杂度O(n),单次查询O(1)。适合查询量极大的场景:只要查询总次数超过logn量级,该方案的整体运行效率就高于二分方案。
补充实现细节:上一个5的索引数组从左到右遍历生成,下一个6的索引数组需要从右到左反向遍历生成:末尾元素如果是6则存当前索引,否则继承后一位的计算值;如果对应位置没有符合要求的元素,统一存-1(无前置5)或数组长度(无后置6),查询时无需额外判断边界。 - 索引收集+二分查找方案
预处理时间复杂度O(n),空间复杂度O(k)(k为数组中5和6的总个数),单次查询O(logk)。适合数组极长、5和6占比极低、查询量较小的场景:比如数组长度为1e7,但5和6的总个数仅为1e3,此时该方案的空间开销远小于预处理数组方案,单次二分仅需10次左右运算,性价比更高。
如果你的场景是数组元素会动态修改的动态场景,可以采用线段树维护区间最值来实现,时间复杂度为预处理O(n)、单次修改O(logn)、单次查询O(logn),但静态场景下没有必要引入额外复杂度。
内容的提问来源于stack exchange,提问作者Garrick
相关产品推荐
相关产品推荐

