文章/答案/技术大牛

发布

社区首页 >问答首页 >数组中所有可能的数字对的差异

问数组中所有可能的数字对的差异
EN

Stack Overflow用户

提问于 2022-10-29 20:22:42

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

假设我有一个反向排序的双打列表：{3, 2, 1}

我想找出可能的数对之间的所有正差之和。在这种情况下，这将是(3-2)+(3-1)+(2-1) = 4。

我知道遍历所有对都是一种选择，但这需要O(n^2)时间。有更好的算法吗？

This是一个非常类似的问题，已经得到了解答，但我无法找到如何将其应用于差分而不是和。

arrays

algorithm

difference

回答 1

Stack Overflow用户

回答已采纳

发布于 2022-10-29 20:35:54

排序列表中的i-th元素(带有i = 0 .. n-1)将为

times

substracted
从sum i times

添加到sum n-i-1 i

所以你可以简单的做

let sum = 0;
for (let i = 0; i < n; i++)
  sum = sum + (n-i-1) * list[i] - i * list[i]

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/74248564

复制

相似问题

问数组中所有可能的数字对的差异
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问数组中所有可能的数字对的差异EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问数组中所有可能的数字对的差异
EN