我最近遇到了一個演算法問題，但我仍然無法想出解決它的方法。任何人都可以幫助使用偽代碼或邏輯嗎？
這是一個問題： 陣列中有n個元素。N是奇數。當我們從陣列中排除 1 個元素時，我們會找到最小的配對成本。
規則：
1 <= n <= 1001
n % 2 = 1
例子：
給定陣列是 [4, 2, 1, 7, 8]
當我們將專案與最接近的專案配對時，[[1,2]、[7,8]] 和“4”被排除在外。所以最小成本是|1 - 2| |7 - 8| = 2;
我嘗試了什么：
- 先排序陣列：[1,2,4,7,8]
- 移除中間元素：4
- 將專案與下一個配對：[[1, 2], [7, 8]]
根據示例它可以作業，但是如果給定陣列是 [1, 7, 8, 16, 17] 怎么辦？
- 首先對陣列進行排序：[1, 7, 8, 16, 17]
- 移除中間元素：8
- 將專案與下一個配對：[[1, 7], [16, 17]]錯誤答案
- 必須排除“1”，并且對必須是 [[7, 8], [16, 17]]
uj5u.com熱心網友回復：
陣列排序后，您可以將所有元素從左到右配對，跟蹤總和，并將最后一個配對替換為從右開始的配對，如果總和較小，則更新總和。
在偽代碼中（所有從零開始的索引）：
let S be the sum of all pairing costs of
elements 2i and 2i 1 for i from 0 to (n-3)/2
(that is all pairings when you exclude the very last element)
let j = (n-1)/2
for i from (n-3)/2 to 0 (included):
let L be the pairing cost of elements 2i and 2i 1
let R be the pairing cost of elements 2i 1 and 2i 2
let S' = S - L R
if S' < S
replace S with S'
replace j with i
2j is the element to exclude
uj5u.com熱心網友回復：
首先對陣列進行排序是一個好的開始。完成此操作后，您可以選擇從索引 1..N 中洗掉任何值。蠻力方法是計算省略索引 1 的配對成本，然后重新計算僅省略索引 2，依此類推，直到達到索引 N。
你會一遍又一遍地計算許多對。為避免這種情況，請考慮省略索引左側的所有對都是奇偶配對（從元素 1 開始的角度來看），而省略索引右側的所有對都是奇偶配對。如果將左配對的總和和右配對的總和預先計算到兩個陣列中，則可以將每個位置的最小成本確定為這兩個陣列每個位置的兩個值的最小總和。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514863.html
標籤：算法
上一篇：如何在二維陣列中找到唯一的數字