查找将数组转换为算术级数的最低成本
我最近在一次采访中遇到了这个问题。 我无法真正想出一个算法。
给定一个未排序的整数数组，我们必须找到该数组可以转换为算术级数的最小代价，如果数组中有任何元素发生了变化，则会产生1单位的代价。 此外，元素的值介于（-inf，inf）之间。
我有点意识到可以在这里使用DP，但我无法解决这个问题。 这些值有一些限制，但我不记得它们。 我只是在寻找高级别的伪代码。
路易斯里奇有一个正确的基本思想，即寻找最大的现有算术级数，但假设它必须单次出现，实际上这种级数的元素可以出现在任何子级的位置上，例如：
1 42 3 69 5 1111 2222 8
只需要4次更改：
42 69 1111 2222
1 3 5 8
要计算此值，请注意每个AP都有一个最右边的元素。 我们可以假设输入向量的每个元素i依次是最右边的AP位置，并且对于每个这样的我考虑位于i左边的所有位置j，确定每个（i，j）组合隐含的步长大小，并且当这是整数（表示一个有效的AP），加上一个暗示这个步长的元素的数量并且在位置i结束 - 因为所有这些元素都属于同一个AP。 整体最大值是当时最长的AP：
struct solution {
int len;
int pos;
int step;
};
solution longestArithProg(vector<int> const& v) {
solution best = { -1, 0, 0 };
for (int i = 1; i < v.size(); ++i) {
unordered_map<int, int> bestForStep;
for (int j = 0; j < i; ++j) {
int step = (v[i] - v[j]) / (i - j);
if (step * (i - j) == v[i] - v[j]) {
// This j gives an integer step size: record that j lies on this AP
int len = ++bestForStep[step];
if (len > best.len) {
best.len = len;
best.pos = i;
best.step = step;
}
}
}
}
++best.len; // We never counted the final element in the AP
return best;
}
上面的C ++代码使用O（n ^ 2）时间和O（n）空间，因为它循环遍历每一对位置i和j，为每个位置执行单个哈希读取和写入。 要回答原始问题：
int howManyChangesNeeded(vector<int> const& v) {
return v.size() - longestArithProg(v).len;
}
编辑这是一个正确的解决方案，不幸的是，虽然很容易理解它不是非常有效的O（n ^ 3）。
function costAP(arr) {
if(arr.length < 3) { return 0; }
var minCost = arr.length;
for(var i = 0; i < arr.length - 1; i++) {
for(var j = i + 1; j < arr.length; j++) {
var delta = (arr[j] - arr[i]) / (j - i);
var cost = 0;
for(var k = 0; k < arr.length; k++) {
if(k == i) { continue; }
if((arr[k] + delta * (i - k)) != arr[i]) { cost++; }
}
if(cost < minCost) { minCost = cost; }
}
}
return minCost;
}
给定未分类整数的数组a = [a_1, a_2, ..., a_n] ，令diffs = [a_2-a_1, a_3-a_2, ..., a_n-a_(n-1)] 。
在diffs查找最大发生值，并在必要时调整任何值， a使所有相邻值的差异达到此数量。
上一篇: Find minimum cost to convert array to arithmetic progression