給定一個陣列 A，大小為 N，包含從 0 到 N 的數字。對于從第 0 個索引開始的每個子陣列，假設 Si，我們說 Bi 是 Si 中不存在的最小非負數。
我們需要找到這個陣列的所有 Bi 的最大可能和。
我們可以重新排列陣列以獲得最大和。
例如：
A = 1, 2, 0 , N = 3
然后假設我們將其重新排列為 A= 0, 1, 2
S1 = 0, B1= 1
S2 = 0,1 B2= 2
S3 = 0,1,2 B3= 3
因此總和是 6
無論我嘗試過什么示例，我都看到排序后的陣列將給出最大的總和。我在這里是正確還是遺漏了什么。
請幫助找到此問題的正確邏輯。我不是在尋找最佳解決方案，而只是在尋找正確的邏輯。
uj5u.com熱心網友回復：
是的，對陣列進行排序會使 ?? ??的總和最大化
由于輸入大小為 ??，它不包括 {0, ..., ??} 范圍內的每個數字，因為那是一組 ?? 1 個數字。假設它只缺少價值 ??，那么 ?? ??對于所有 ?? >= ?? 都是 ??。如果缺少其他數字，但大于 ??，則對任何 ?? ??沒有影響。
因此我們需要在 {0, ..., ??} 范圍內找出最小缺失值 ??。然后最大的和是 1 2 ... ?? (?????)??。這是??(?? 1)/2 (?????)?? = ??(1 2?? - ??)/2
要找到 ?? 的值，請創建一個大小為 ?? 1 的布爾陣列，并在輸入中遇到 ?? 時將索引 ?? 處的條目設定為 true。?? 然后是該布爾陣列仍然具有錯誤值的第一個索引。
這是 JavaScript 片段中的一個小實作：
function maxSum(arr) {
const n = arr.length;
const isUsed = Array(n 1).fill(false);
for (const value of arr) {
isUsed[value] = true;
}
const k = isUsed.indexOf(false);
return k * (1 2*n - k) / 2;
}
console.log(maxSum([0, 1, 2])); // 6
console.log(maxSum([0, 2, 2])); // 3
console.log(maxSum([1, 0, 1])); // 5轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498190.html
上一篇：C#中二維陣列的方差和平均值