You need to enable JavaScript to run this app. 数组指定索引对应上一个5、下一个6的索引查找优化方案咨询
优惠活动
大模型
产品
解决方案
定价
更多

数组指定索引对应上一个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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.17 02:54:03