สมมติว่าเรามีจำนวนอาร์เรย์ที่มีความยาวถึงขีด จำกัด ของค่าอื่น ในการย้ายครั้งเดียว เราสามารถแทนที่ค่าใดๆ จาก nums ด้วยค่าอื่นระหว่าง 1 ถึงขีดจำกัด ซึ่งรวมถึง อาร์เรย์กล่าวกันว่าเป็นส่วนเสริมหากสำหรับดัชนี i ทั้งหมด nums[i] + nums[n-1-i] เท่ากับตัวเลขเดียวกัน ดังนั้นเราจึงต้องหาจำนวนการเคลื่อนไหวขั้นต่ำที่จำเป็นในการเสริมจำนวน
ดังนั้น หากอินพุตเท่ากับ nums =[1,4,2,3] จำกัด =4 เอาต์พุตจะเป็น 1 เพราะในการย้ายครั้งเดียว เราสามารถสร้างองค์ประกอบที่ดัชนี 1 ถึง 2 ได้ ดังนั้นอาร์เรย์จะเป็น [1,2 ,2,3], จากนั้น nums[0] + nums[3] =4, nums[1] + nums[2] =4, nums[2] + nums[1] =4, nums[3] + nums[ 0] =4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของ nums
- กลาง :=ผลหารของ n/2
- zero_moves :=แผนที่ว่างของค่าประเภทจำนวนเต็ม
- start :=อาร์เรย์ขนาด (2 * จำกัด + 1) และเติมด้วย 0
- end :=อาร์เรย์ขนาด (2 * จำกัด + 1) และเติมด้วย 0
- res :=อินฟินิตี้
- สำหรับฉันในช่วง 0 ถึงกลาง - 1 ทำ
- x :=nums[i]
- y :=nums[n - 1 - i]
- zero_moves[x + y] :=zero_moves[x + y] + 1
- เพิ่มจุดเริ่มต้น[1 + ขั้นต่ำของ x, y] ขึ้น 1
- เพิ่มจุดสิ้นสุด[จำกัด + สูงสุดของ x, y] ขึ้น 1
- ช่วงเวลา :=0
- สำหรับเป้าหมายในช่วง 2 เพื่อจำกัด*2 ทำ
- ช่วงเวลา :=ช่วงเวลา + เริ่ม[เป้าหมาย]
- ค่าใช้จ่าย :=2 *(ช่วงกลาง - ช่วงเวลา) + ช่วงเวลา - zero_moves[เป้าหมาย]
- res :=ขั้นต่ำของความละเอียดและต้นทุน
- ช่วงเวลา :=ช่วงเวลา - สิ้นสุด[เป้าหมาย]
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
