寻找将数组转换为算术级数的最低成本 [英] Find minimum cost to convert array to arithmetic progression

问题描述

我最近在一次采访中遇到了这个问题。我真的不能为此提出一个算法。

I recently encountered this question in an interview. I couldn't really come up with an algorithm for this.

给出一个未排序的整数数组，我们必须找到将该数组转换为的最小开销算术级数，其中如果更改数组中的任何元素，则成本为1单位。同样，元素的值在（-inf，inf）之间。

Given an array of unsorted integers, we have to find the minimum cost in which this array can be converted to an Arithmetic Progression where a cost of 1 unit is incurred if any element is changed in the array. Also, the value of the element ranges between (-inf,inf).

我意识到可以在此处使用DP，但是我无法解决方程式。值有一些限制，但我不记得了。我只是在寻找高级伪代码。

I sort of realised that DP can be used here, but I couldn't solve the equation. There were some constraints on the values, but I don't remember them. I am just looking for high level pseudo code.

推荐答案

EDIT
这是正确的不幸的是，该解决方案虽然简单易懂，但在O（n ^ 3）时效率不高。

EDIT Here's a correct solution, unfortunately, while simple to understand it's not very efficient at 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;
}

• 找到相对的 delta 数组中每个索引对之间的距离


• 使用相对增量来测试使用该 delta
  
• 返回最低费用


• Find the relative delta between every distinct pair of indices in the array
• Use the relative delta to test the cost of transforming the whole array to AP using that delta
• Return the minimum cost

这篇关于寻找将数组转换为算术级数的最低成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！