Python程序：计算已排序列表中每对数字绝对差之和

假设我们有一个名为nums的已排序数字列表，我们需要找到给定列表中每对数字之间绝对差的总和。这里我们将(i, j)和(j, i)视为不同的对。如果答案非常大，则将结果模10^9+7。

因此，如果输入类似于nums = [2, 4, 8]，则输出将为24，因为|2 - 4| + |2 - 8| + |4 - 2| + |4 - 8| + |8 - 2| + |8 - 4|。

为了解决这个问题，我们将遵循以下步骤：

  • m = 10^9 + 7

  • total := 0

  • 对于 i 从0到nums的大小，执行：

    • total := (total + (i * nums[i] - (nums的大小 - 1 - i) * nums[i])) mod m

  • 返回 (2 * total) mod m

让我们来看下面的实现，以便更好地理解：

示例

 在线演示

class Solution:
   def solve(self, nums):
      m = 10**9 + 7
      total = 0
      for i in range(len(nums)):
         total += (i*nums[i] - (len(nums) - 1 - i)*nums[i]) % m
      return (2*total) % m
ob = Solution()
nums = [2, 4, 8]
print(ob.solve(nums))

输入

[2, 4, 8]

输出

24

更新于：2020年10月7日

173 次浏览

开启你的职业生涯

完成课程，获得认证

开始学习
广告