问重新排列列表以满足条件
EN

Stack Overflow用户

提问于 2022-07-05 06:33:43

回答 1查看 51关注 0票数 0

我在一次编码面试中被问到这个问题，但没能解决这个问题。任何指点都会很有帮助。

我得到了一个整数列表(把它看作一个数字行)，它需要重新排列，以便元素之间的差异等于M (给定的整数)。需要重新排列列表，以便将max absolute difference between the elements' new positions and the original positions的值降到最低。最后，返回此值乘以2。

测试用例：

//1.
original_list = [1, 2, 3, 4]
M = 2
rearranged_list = [-0.5, 1.5, 3.5, 5.5]
// difference in values of original and rearranged lists
diff = [1.5, 0.5, 0.5, 1.5]
max_of_diff = 1.5 // list is rearranged in such a way so that this value is minimized
return_val = 1.5 * 2 = 3 

//2. 
original_list = [1, 2, 4, 3]
M = 2
rearranged_list = [-1, 1, 3, 5]
// difference in values of original and rearranged lists
diff = [2, 1, 1, 2]
max_of_diff = 2 // list is rearranged in such a way so that this value is minimized
return_val = 2 * 2 = 4 

Constraints:
1 <= list_length <= 10^5
1 <= M <= 10^4
-10^9 <= list[i] <= 10^9

关于leetcode有一个非常类似的问题：https://leetcode.com/problems/minimize-deviation-in-array/，但是在这里，在数组上执行的操作被提到，而这里没有提到。我真的很困惑。

algorithm

云点播特惠1元起

提供制作上传、存储、转码、媒体处理、媒体 AI、加速分发播放、版权保护等一体化的高品质媒体服务

回答 1

Stack Overflow用户

回答已采纳

发布于 2022-07-05 07:17:41

下面是你如何看待它的方法：

“后置”列表就像一条直线，其斜率对应于M。

下面是第一个示例的可视化：

黑点是输入值1，2，3，4，其中数组的索引是X坐标，而该索引的实际值是Y坐标。

绿线由M确定。最初，这条线在(0，0)处穿过原点。红线段表示必须考虑的差异。

现在绿线必须垂直移动到它的最佳位置。我们可以看到，我们只需要看看它对第一点和最后一点所产生的影响。另外两种投入永远不会造成极端。这通常是正确的:只有两个输入元素需要考虑。它们是最大的(签署的--不是绝对的)差别和最小的差别。

我们可以看到，我们需要以这样一种方式移动绿线，即与这两个极端的符号差异是相互对立的，即它们的绝对差异是相同的，但符号是相反的。

这种绝对差异是我们需要返回的两倍，它实际上是最大(有符号)差和最小(有符号)差之间的区别。

因此，最后，我们必须生成绿线上的值，找出与数据点(Y-坐标)的最小和最大(有符号)差，并返回两者之间的差值。

下面是JavaScript中的一个实现，运行您提供的两个示例：

function solve(y, slope) {
    let low = Infinity;
    let high = -Infinity;
    for (let x = 0; x < y.length; x++) {
        let dy = y[x] - x * slope;
        low = Math.min(low, dy);
        high = Math.max(high, dy);
    }
    return high - low;
}

console.log(solve([1, 2, 3, 4], 2)); // 3
console.log(solve([1, 2, 4, 3], 2)); // 4