gpt4 book ai didi

algorithm - 有效查找高密度区间的最佳数据结构

转载 作者:行者123 更新时间:2023-12-04 09:16:01 25 4
gpt4 key购买 nike

我有一组未排序的整数和一个间隔长度。我需要找到给定区间中包含的最大元素子集
示例 1:

Set: [11, 1, 2, 100, 12, 14, 99]

Interval: 4

Result: [11, 12, 14]
示例 2:
Set: [1, 100, 55, 2, 88, 3]

Interval: 10

Result: [1, 2, 3]
在实践中,集合中有更多的元素
解决这个问题的有效数据结构和算法是什么?

最佳答案

  • 将整数集排序为数组 A并让 w是我们间隔的宽度。
  • 初始化 i = j = best_start = best_n = 0 .
  • 增量 j只要A[j] < A[i] + w (或 <= 取决于您定义间隔的方式)。
  • j - i > best_n套装best_start = ibest_n = j - i .
  • 增量 i = i + 1如果 i, j < length(A)回到2。

  • 总复杂度由初始排序复杂度 O(n log n) 决定。排序后注意复杂度必须是线性的,因为 j < n只能增加,我们在每一步都做恒定数量的事情。

    关于algorithm - 有效查找高密度区间的最佳数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63213662/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com