寻找将数组转换为算术级数的最低成本

本文介绍了寻找将数组转换为算术级数的最低成本的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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