将数组转换为等差数列的最小成本是多少

Question

我最近在面试中遇到了这个问题，但我无法为其设计出一个算法。

给定一个未排序的整数数组，我们需要找到将此数组转换为等差数列所需的最小成本。如果更改数组中的任何元素，则需要支付1个单位的成本。此外，元素的值范围在(-inf,inf)之间。

我意识到可以使用动态规划解决这个问题，但是我无法解决方程式。对值有一些限制，但我不记得它们是什么。我只需要高层次的伪代码。

- John Lui

---

是否允许交换或者只能进行逐个元素的算术操作？ - sunny

这更像是一个线性回归。 - sunny

Answer 1

编辑 这里有一个正确的解决方案，虽然简单易懂，但其时间复杂度为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;
}

• 找出数组中每个不同索引对之间的相对增量
• 使用相对增量来测试将整个数组转换为AP的成本
• 返回最小成本

- Louis Ricci

---

你对寻找现有算术进度的见解是正确的，但恐怕没有什么限制它只能在一个序列中出现，因此相邻差异并不是非常有信息量的。例如，在[1, 42, 3, 69, 5]中，可以仅花费2来更改42和69。目前为止是-1。 - j_random_hacker

@j_random_hacker - 我已经添加了一个始终正确的解决方案。 - Louis Ricci

Answer 2

Louis Ricci 的基本想法是寻找最大的等差数列，但他假设这个等差数列必须出现在单次运行中，实际上这个等差数列的元素可以出现在任何位置的子集中，例如：

1 42 3 69 5 1111 2222 8

只需要进行四个更改：

  42   69   1111 2222
1    3    5           8

为了计算这个，需要注意每个等差数列都有一个最右边的元素。我们可以假设输入向量中的每个元素i依次是最右边的等差数列位置，并对每个i考虑到i左侧的所有位置j，确定每个(i,j)组合所暗示的步长，并在此为整数（表示有效的等差数列）时将暗示该步长并以i为结尾的元素数量加1——因为所有这样的元素属于同一个等差数列。然后，最长的等差数列就是所有这些元素数量的最大值：

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;
}

- j_random_hacker

---

这是一个更加高效的答案。 - Louis Ricci

Answer 3

这个问题有一个简单的几何解释，表明它可以在O(n^2)时间内解决，可能无法比这更快（从3SUM归约）。假设我们的数组是[1, 2, 10, 3, 5]。我们可以将该数组写成一系列点的序列。

(0,1), (1,2), (2,10), (3,3), (4,5)

其中x值是数组项的索引，y值是数组项的值。现在的问题是找到一条通过该集合中最大可能数量的点的线。将数组转换的成本是不在一条直线上的点的数量，当在一条直线上的点的数量最大化时，这个成本最小化。

这个SO帖子给出了一个相当明确的答案：什么是找到经过大多数点的直线最有效的算法？

思路：对于集合中从左到右的每个点P，找到通过该点和P右侧的最大点数的线。(我们不需要查看P左侧的点，因为它们会在早期迭代中被捕获)。

为了找到P右侧最大数量的共线点，对于每个这样的点Q，计算线段PQ的斜率。在哈希映射中累加不同的斜率。映射到最大命中次数的斜率就是你要找的。

技术问题：您可能不希望使用浮点算术来计算斜率。另一方面，如果您使用有理数，则可能需要计算最大公约数以比较分数（通过比较分子和分母），这将使运行时间乘以log n的因素。相反，您应该通过测试是否ad == bc来检查有理数a/b和c/d的相等性。

上面引用的SO帖子给出了从3SUM归约的方法，即该问题是3SUM-hard的，这表明如果可以比O(n^2)更快地解决此问题，则3SUM也可以比O(n^2)更快地解决。这就是整数在(-inf，inf)中的条件适用的地方。如果已知整数来自有界集，则对3SUM的归约并不明确。

一个有趣的进一步问题是，当整数处于有界集(-N，N)时，维基百科中用于在O(n + N log N)时间内解决3SUM的想法是否可用于更快地解决将数组转换为AP问题的最小成本，而不是O(n^2)。

- Edward Doolittle

---

你似乎在描述与我提供的算法非常相似的内容，不同之处在于(a) 我检查 P 左侧的点（而不是右侧），以及(b) 我们可以忽略斜率为非整数的线段（假设元素必须保持为整数），所以我这样做，而不是使用 FP 或有理数。另外，你的简化目前的方式是错误的 - 它需要将问题 从 通过最大点的链接直线问题 转换为 你提供的特殊情况（即相同的问题，但 x 坐标限制为 1、2、3，...）。 - j_random_hacker

@j_random_hacker，当然，你说得对，斜率是有理数！我应该想到的。不过，如果我们允许包含未定义元素（对应缺失点）的数组（其更改成本为0），那么减少的方向也是直接的，我相信你也是正确的。我会再仔细思考一下的。 - Edward Doolittle

Answer 4

给定未排序整数数组 a = [a_1, a_2, ..., a_n]，令 diffs = [a_2-a_1, a_3-a_2, ..., a_n-a_(n-1)]。

找到 diffs 中出现最多的值，并将 a 中必要的值调整，以便所有相邻的值之间差异为该值。

- Tony Tuttle

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Erick G. Hagstrom

你的算法需要更多的梳理：a = [1,2,3,5,7,8,9,10]，diffs = [1,1,2,2,1,1,1]，maxRecurringDiff = 5（1出现了5次）。如果你从开头开始调整值，那么你的成本是5，但如果你从结尾开始调整值，你的成本就是4（将1、2、3、4改为3、4、5、6）。 - Louis Ricci

我忽略了两个有效的观点。我看到@LouisRicci发布的解决方案解决了这些问题。 - Tony Tuttle

Answer 5

有趣的是，我今天在校园招聘测试中也遇到了同样的问题。在做测试的过程中，我意识到基于数组中两个相邻元素之间最频繁差异来改变元素的逻辑在某些情况下会失败。 例如-4、5、8、9。根据上述提出的a2-a1、a3-a2的逻辑，答案应该是1，但事实并非如此。 正如你建议的DP一样，我认为可以考虑每个元素的两个值-修改时的成本和不修改时的成本，并返回其中较小的值。最后，在到达数组末尾时终止。

- user5179052