寻找Double类型时间间隔列表中含最多元素的0.05s区间

我现在要处理一组无序的Double类型时间间隔列表，列表最多包含100个围绕1波动的值，示例为[0.897, 0.912, ... 1.214, 0.981]。我的需求是找出其中包含元素数量最多的0.05秒区间。

我自己写了一段代码（如下），虽然测试数据上有效，但每次遍历整个列表的方式太冗余，处理更大列表时问题会更明显，希望得到更优雅的解法，比如借助绘图相关的思路？

var lowerEnd = 0.5
var higherEnd = 1.5
var numberOfElements = 0
var currentMost = 0
var mostCommonRange = 0.0

while(lowerEnd < higherEnd) {
    records.forEach { entry ->
        if(lowerEnd <= entry && entry < (lowerEnd + 0.05)) {
            numberOfElements += 1
        }              
    }
    if(numberOfElements > currentMost) {
        currentMost = numberOfElements
        mostCommonRange = lowerEnd
    }
    numberOfElements = 0
    lowerEnd += .05
}

优化方案 #

方案一：排序+滑动窗口（高效灵活） #

原方法的问题是每个区间都要全量遍历列表，时间复杂度为O(n*m)（n是元素数，m是区间数量）。排序后用滑动窗口可以将时间复杂度降到O(n log n) + O(n)，效率提升明显。

思路：

1. 排序列表：将无序的时间间隔排序后，元素按从小到大排列，方便用双指针维护有效区间。
2. 滑动窗口统计：用右指针逐个遍历元素，调整左指针使得窗口内所有元素都落在[当前右元素-0.05, 当前右元素)的区间内，此时窗口的长度就是该区间的元素数量，记录最大数量和对应的区间起点。

代码实现：

fun findMostDenseInterval(records: List<Double>, interval: Double = 0.05): Pair<Double, Int> {
    if (records.isEmpty()) return 0.0 to 0

    val sortedRecords = records.sorted()
    var left = 0
    var maxCount = 0
    var bestStart = 0.0

    for (right in sortedRecords.indices) {
        // 调整左指针，确保窗口内元素都在有效区间内
        while (sortedRecords[right] - sortedRecords[left] >= interval) {
            left++
        }
        val currentCount = right - left + 1
        if (currentCount > maxCount) {
            maxCount = currentCount
            // 区间起点取右元素减去区间长度，保证覆盖窗口内所有元素
            bestStart = sortedRecords[right] - interval
        }
    }
    return bestStart to maxCount
}

方案二：直方图统计（贴近绘图思路） #

如果你想贴近“绘图相关思路”，可以用直方图分组统计的方式：将数据按0.05的区间分组，统计每个区间的元素数量，再找出元素最多的区间。这个方法只需要遍历一次列表，时间复杂度O(n)，但需要预先知道数据的范围。

思路：

1. 划分区间：根据已知的范围（0.5到1.5），将其划分为(1.5-0.5)/0.05=20个0.05长度的区间。
2. 统计每个区间的元素数：遍历列表，将每个元素分配到对应的区间并计数。
3. 找出最大计数的区间：遍历计数数组，找到元素最多的区间起点。

代码实现：

fun findMostDenseIntervalHistogram(records: List<Double>, interval: Double = 0.05, min: Double = 0.5, max: Double = 1.5): Pair<Double, Int> {
    val intervalCount = ((max - min) / interval).toInt()
    val counts = IntArray(intervalCount) { 0 }

    records.forEach { value ->
        if (value in min until max) {
            val index = ((value - min) / interval).toInt()
            counts[index]++
        }
    }

    var maxCount = 0
    var bestIndex = 0
    counts.forEachIndexed { index, count ->
        if (count > maxCount) {
            maxCount = count
            bestIndex = index
        }
    }

    val bestStart = min + bestIndex * interval
    return bestStart to maxCount
}

内容的提问来源于stack exchange，提问作者Alex