最小化阵列的无序系数(差的绝对值之和)
最小化阵列的无序系数(差的绝对值之和)
提问于 2017-11-01 18:36:33
我遇到了一个来自波兰奥林匹亚的问题:每个数组a1,a2,a3 ... a4都有它的无序系数K，等于|a[1]-a[2]| + |a[2]- a[3]| + |a[3]-a[4]| ... |a[n-1] -a[n]|。对于每个元素，我们应该计算出通过与数组的任何其他元素交换位置可以得到的最小K。示例:给定数组7 4 5 2 5。该阵列的初始无序系数为10 = |7-4|+|4-5|+|5-2|+|2-5|，用第4元：|2-4|+|4-5|+|5-7|+|7-5| = 7交换后，得到第1元的最小无序系数。我们需要计算数组的所有元素。复杂性应该是O(nlogN)。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-11-01 21:13:45
只需对数组进行排序，并计算这个排序数组的无序系数。它是阵列的MDC。
它是如何工作的。您需要将差异最小的元素组合在一起。排序会给出这个结果。
也试图证明这一理论:)明天将更新。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/47061516
复制相关文章
相似问题
腾讯云开发者
