arrays - 给定一个整数数组，以近似相等的距离调整数组的大小

Question

给定一个像这样的数字数组:

[0, 99, 299, 498, 901]

我可以使用什么算法将该数组的大小调整为数组之间距离大致相等的数组。或者换句话说，用近似最大公倍数重新采样。因此，在上面的示例中，最大公约数大约 100，因此结果将是:

[0, 99, 200, 299, 400, 498, 600, 700, 800, 901]

使用原始值会很好，并且可以设置误差线(上面的解决方案将误差设置为 2)，但也会对此结果感到满意:

[0, 100, 200, 300, 400, 500, 600, 700, 800, 900]

2017 年 1 月 12 日更新

根据 Redu 的回答，这里是他的代码的 Swift 版本:

var arr: [Int] = [0, 99, 299, 498, 901]

var diffs = [Int]()
var minGap: Int = 0
for x in 0..<arr.count-1 {
    let gap = arr[x+1] - arr[x]
    diffs.append(gap)
    if minGap == 0 || minGap > gap {
        minGap = gap
    }
}

var resamples = [Int]()
for item in arr {
    if let lastSample = resamples.last {
        let n = Int((Float(item - lastSample) / Float(minGap)).rounded())
        let g = (item - lastSample) / n
        var inserts = [Int]()
        for x in 0..<n-1 {
            let newSample = lastSample + ((x+1) * g)
            inserts.append(newSample)
        }
        resamples.append(item)
        resamples.append(contentsOf: inserts)
    } else {
        resamples.append(item)
    }
}

Answer 1

本质上，您想对算术级数使用最小二乘回归。

算术级数可以用 3 项参数化:第一项、最后一项和公差。这 3 项将构成您的目标函数的参数，您将寻求将其最小化。

在每个优化步骤中，您需要选择试验算术级数中的哪些项需要针对原始集合进行回归。这将是相当具有挑战性的，但幸运的是这两个系列都会被排序，所以这应该是一个 O(N) 遍历。

围绕这 3 个术语的约束是一组打印上令人满意的术语。例如，即使源系列是 99、297，100、200、300 是否会优先于 99、198、297？

完整的答案我会觉得太宽泛 - 并且可能至少需要一周的工作。但这就是我开始这个项目的方式。