สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums ความยาวของรายการนี้เท่ากัน ตอนนี้ให้พิจารณาการดำเนินการที่เราเลือกตัวเลขใดๆ ใน nums และอัปเดตด้วยค่าในช่วง [1 และสูงสุด nums] เราต้องหาจำนวนขั้นต่ำของการดำเนินการดังกล่าวที่จำเป็นสำหรับทุกๆ i nums[i] + nums[n-1-i] เท่ากับจำนวนเดียวกัน
ดังนั้น หากอินพุตเท่ากับ nums =[8,6,2,5,9,2] ผลลัพธ์จะเป็น 2 เพราะหากเราเปลี่ยน 2 ตัวแรกที่ nums[2] เป็น 5 และ 9 ที่ nums[4 ] ถึง 4 จากนั้นองค์ประกอบจะเป็น [8,6,5,5,4,2] จากนั้น nums[i] + nums[n-1-i] สำหรับแต่ละ i จะเป็น (8+2) =( 6+4) =(5+5) =10.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- N :=ขนาดของ nums
- mx :=สูงสุดของ nums
- เหตุการณ์ :=รายการใหม่
- idx :=0
- ในขณะที่ idx <ชั้นของ N / 2 ทำ
- a :=nums[idx]
- b :=nums[N - idx - 1]
- แทรกคู่ (ขั้นต่ำ (a + 1), (b + 1), 1) ที่ส่วนท้ายของกิจกรรม
- ใส่คู่ (a + b, 1) ที่ส่วนท้ายของกิจกรรม
- แทรกคู่ (a + b + 1, -1) ที่ส่วนท้ายของกิจกรรม
- ใส่คู่ (สูงสุด (a + mx) และ (b + mx + 1), -1) ที่ส่วนท้ายของเหตุการณ์
- idx :=idx + 1
- จัดเรียงรายการกิจกรรม
- ปัจจุบัน :=0
- mx_same :=0
- สำหรับแต่ละคู่ (เหตุการณ์ เดลต้า) ในเหตุการณ์ ทำ
- ปัจจุบัน :=ปัจจุบัน + เดลต้า
- mx_same :=สูงสุดของกระแสและ mx_same
- ส่งคืน N - mx_same
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(nums): N = len(nums) mx = max(nums) events = [] idx = 0 while idx < N // 2: a = nums[idx] b = nums[N - idx - 1] events.append((min(a + 1, b + 1), 1)) events.append((a + b, 1)) events.append((a + b + 1, -1)) events.append((max(a + mx, b + mx) + 1, -1)) idx += 1 events.sort() current = 0 mx_same = 0 for event, delta in events: current += delta mx_same = max(current, mx_same) return N - mx_same nums = [8,6,2,5,9,2] print(solve(nums))
อินพุต
[6, 8, 5, 2, 3]
ผลลัพธ์
2
