โปรแกรมหาการเคลื่อนย้ายน้อยที่สุดเพื่อทำให้อาร์เรย์ complementary ใน Python

ปัญหา

อาร์เรย์ nums ความยาวคู่ และ limit หนึ่งการเคลื่อนย้าย: เปลี่ยนค่าใดๆ ใน nums เป็น 1..limit อาร์เรย์ complementary ถ้า nums[i] + nums[n-1-i] เท่ากันทุก i หาจำนวนการเคลื่อนย้ายน้อยที่สุด

ตัวอย่าง

nums=[1,4,2,3], limit=4 → ผลลัพธ์ 1 (เปลี่ยน index 1 เป็น 2 → [1,2,2,3] ผลรวมคู่ = 4 ทุกคู่)

ขั้นตอนการแก้ปัญหา

1. n := len(nums), mid := n//2
2. zero_moves := defaultdict(int), start, end := arrays size 2*limit+1
3. สำหรับ i 0 ถึง mid-1:
   • x := nums[i], y := nums[n-1-i]
   • zero_moves[x+y] += 1
   • start[min(x,y)+1] += 1
   • end[max(x,y)+limit] += 1
4. intervals := 0, res := inf
5. วน target 2 ถึง 2*limit:
   • intervals += start[target]
   • cost := 2*(mid - intervals) + intervals - zero_moves[target]
   • res = min(res, cost)
   • intervals -= end[target]
6. คืน res

การนำไปใช้งาน (Python)

from collections import defaultdict
def solve(nums, limit):
    n = len(nums)
    mid = n // 2
    zero_moves = defaultdict(int)
    start = [0] * (2 * limit + 1)
    end = [0] * (2 * limit + 1)
    res = float('inf')
    for i in range(mid):
        x = nums[i]
        y = nums[n - 1 - i]
        zero_moves[x + y] += 1
        start[min(x, y) + 1] += 1
        end[max(x, y) + limit] += 1
    intervals = 0
    for target in range(2, limit * 2 + 1):
        intervals += start[target]
        cost = 2 * (mid - intervals) + intervals - zero_moves[target]
        res = min(res, cost)
        intervals -= end[target]
    return res

nums = [1,4,2,3]
limit = 4
print(solve(nums, limit))

อินพุต

[1,4,2,3], 4

เอาต์พุต

1