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

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 个术语将构成您的 objective 函数的参数，您将力求将其最小化。

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

围绕这 3 个术语的约束将是一个排版令人愉悦的集合。例如，即使源序列是 99、297，100、200、300 是否比 99、198、297 更受欢迎？

我觉得完整的答案过于宽泛 - 可能至少需要一周的时间。但这就是我开始这个项目的方式。

Answer 2

以下是我在 JS 中的解决方案。我首先找到最小间隙，然后尝试找出有多少适合 in-between 每个项目并在不改变原始值的情况下进行相应处理。

显然，要使该算法起作用，输入数组必须按升序排序。

var arr = [0, 99, 299, 498, 901],
    gap = Math.min(...Array(arr.length-1).fill().map((_,i) => arr[i+1]-arr[i])),  // Find the minimum gap
    res = arr.reduce((p,c,i) => { var n = Math.round((c-p[p.length-1])/gap);      // Find howmany gaps are inbetween according to the minimum gap
                                      g = Math.round((c-p[p.length-1])/n);        // Calculate the average gap top apply
                                  return i ? p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c)
                                           : p.concat(c);
                                },[]);
console.log(res);

解释：

gap = Math.min(...Array(arr.length-1).fill().map((_,i) => arr[i+1]-arr[i])),

首先我们建立一个比输入数组小一的新数组。 (Array(arr.length-1)) 首先我们用未定义的元素初始化 (.fill()) 它，然后用 arr[i+1]-arr[i] .map() 每个元素。所以现在我们有了 gaps 数组。然后我们将它作为参数传播到 Math.min() 函数中。这是 Math.min(...Array( 部分。所以现在我们在上面给定的情况下的最小差距为 99。

res = arr.reduce((p,c,i) => { var n = Math.round((c-p[p.length-1])/gap);
                                  g = Math.round((c-p[p.length-1])/n);
                              return i ? p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c)
                                       : p.concat(c);
                            },[]);

.reduce()部分看起来有点难看，但很简单。我们的 .reduce() 操作将函数作为参数（通常称为回调函数）并在每次迭代数组项时运行它。这个回调函数是以(p,c,i) => {... }开头的部分。这是一个箭头函数。这与正常功能基本相同。 x => x 表示 function(x) { return x;} 或 x => {return x;}。在我们的例子中，因为我们使用大括号来定义函数的主体（由于多个语句），我们将不得不使用 return 指令。

我们的 .reduce() 使用一个空数组作为初始值。这是最后的 ,[]); 部分。 reduce 将调用每个数组项的回调函数将传递三个参数 (p,c,i) 初始空数组被分配给 p （前一个）参数，当前项被分配给 c 参数，当前索引在每次调用时分配给 i 参数。

在回调的主体中，我们定义了 2 个变量。 n 和 g.

n = Math.round((c-p[p.length-1])/gap);

p[p.length-1] return 是 p 数组的最后一个元素。所以在第一回合；当 i = 0 时，p[0] 是 undefined 并且 Math.round((c-p[p.length-1])/gap); 是 NaN（不是数字）但我们不在乎，因为；

return i ? p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c)
         : p.concat(c);

三元条件表示；

result = condition ? if true do this
                   : if false do this

因此，正如您看到的那样，它会根据条件执行其中一个指令并 returns 结果。在我们的例子中，结果被 returned 作为 p.

的值

所以在我们的例子中，如果 i == 0（JS 中的 false 值）那么只执行 p.concat(c) 和 return 新的 p 值并继续下一次迭代（使用新的 p、c 和 i 值调用回调。

如果 i 不是 false（除 0 以外的任何值），则喜欢

p.concat(Array(Math.round(n-1)).fill().map((_,i) => p[p.length-1] + (i+1)*g),c)

这意味着创建一个大小为许多中间元素的数组，使用 undefineds 初始化数组并使用 p[p.length-1] + (i+1)*g 映射每个元素并将此数组连接到 p 数组并将 c 附加到最后，然后 return p 数组。

提醒一件事：p.concat(whatever...) 指令将 return 一个由 p 的元素组成的新数组和作为参数包含的数组的 "items" 或items 本身包含 ar 参数。我是说；

[1,2,3].concat([4,5,6],[7,8],9) 会导致 [1,2,3,4,5,6,7,8,9]

所以这应该解释清楚了。

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

Given an array of integers, resize the array with approximate equal distances

arrays

algorithm

sampling