โปรแกรมหาผลรวมความต่างสัมบูรณ์ของทุกคู่ในรายการที่เรียงแล้วใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียงแล้ว nums ต้องหาผลรวมความต่างสัมบูรณ์ระหว่างทุกคู่ (i,j) และ (j,i) นับคนละคู่ หากใหญ่ mod 10⁹+7

ตัวอย่าง: nums = [2, 4, 8] ผลลัพธ์ 24 = |2-4|+|2-8|+|4-2|+|4-8|+|8-2|+|8-4|

ขั้นตอนการแก้ปัญหา (Mathematical Formula O(n))

1. m = 10**9 + 7
2. total = 0
3. สำหรับ i จาก 0 ถึง len(nums)-1:
   • total += (i * nums[i] - (len(nums) - 1 - i) * nums[i]) % m
4. คืนค่า (2 * total) % m (คูณ 2 เพราะนับ (i,j) และ (j,i))

หลักการ: แต่ละ nums[i] จะถูกลบ i ครั้ง และถูกบวก n-1-i ครั้ง

ตัวอย่างโค้ด Python

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))  # Output: 24

อินพุต

[2, 4, 8]

เอาต์พุต

24