Chương trình tìm tổng chênh lệch tuyệt đối trong mảng đã sắp xếp trong Python

Cho mảng nums đã sắp xếp không giảm. Tạo mảng result cùng độ dài, result[i] = tổng |nums[i] - nums[j]| cho mọi j.

Ví dụ: nums = [5,7,12], đầu ra = [9, 7, 12].

• |5-5|+|5-7|+|5-12| = 0+2+7 = 9
• |7-5|+|7-7|+|7-12| = 2+0+5 = 7
• |12-5|+|12-7|+|12-12| = 7+5+0 = 12

Giải pháp

Sử dụng prefix sum tính hiệu quả O(n):

• res := [], s := 0, n := len(nums)
• Với i từ 1 đến n-1: s += nums[i] - nums[0]
• Thêm s vào res
• Với i từ 1 đến n-1:
  • diff := nums[i] - nums[i-1]
  • s += diff * i
  • s -= diff * (n-i)
  • Thêm s vào res
• Trả về res

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(nums):
    res = []
    s = 0
    n = len(nums)
    for i in range(1, n):
        s += nums[i] - nums[0]
    res.append(s)
    for i in range(1, n):
        diff = nums[i] - nums[i-1]
        s += diff * i
        s -= diff * (n - i)
        res.append(s)
    return res

nums = [5,7,12]
print(solve(nums))

Đầu vào

[5,7,12]

Đầu ra

[9, 7, 12]