只是試圖解決這個問題：
給定一個未排序的整數陣列，將其最大的 n 個數相加。
我做了一個 TypeScript 實作，但這當然與語言無關：
const list_sum_largest_n_numbers = (list: Array<number> = [], n: number) => {
let sum: number = 0;
const sorted_list = list.sort((a, b) => a - b);
for (let i = 0; i < n; i ) {
let value_to_sum = sorted_list?.pop() || 0;
sum = value_to_sum;
}
return sum;
};
let list = [17, 310, 32_432, 3, 2, 317, 34, 108_379];
let n = 3;
let result = list_sum_largest_n_numbers(list, n);
alert(result); // 141_128
這里在操場上。
我的第一個問題是，在解決這類問題時，Array.sort()是否允許使用語言提供的方法——as——，或者我是否應該自己實作所有東西，保持解決方案的低水平。
另外，我不確定這是解決它的最佳方法。我會說這是 O(n)，但我沒有考慮到Array.sort()我正在使用的方法。
uj5u.com熱心網友回復：
排序已經是O(n logn)。使用內置排序功能時，它可能是一個簡單的解決方案，但它不會是解決問題的最有效解決方案。
如果您正在為這個問題尋找更有效但更簡單的解決方案，您可以通過迭代不斷挑選（并洗掉）最大的數字k次。您可以隨時將它們匯總在一起，而無需將它們存盤在新陣列中并再次迭代。這實際上是每個數字O(n) ，所以總共O(kn)。
這對于小的或恒定的k將更有效。當然，例如，如果您知道k = O(n)，則存在更好的方法。
對于稍微不那么簡單的解決方案，您可以使用Quickselect找到第k個最大的數字x，然后在一次迭代中將所有大于x的數字相加，然后添加x和可能的剩余重復值。這將為您提供O(n)加法運算的總時間復雜度。這是性能和代碼復雜性之間的權衡:)
至于是否可以使用內置函式：可以。每當它們適合您的目的時，最好使用它們而不是每次都重新發明輪子。但是，在學術或挑戰環境中，出于教育或競爭原因，可能存在禁止使用庫或內置功能的規則。
uj5u.com熱心網友回復：
給定陣列a[m]并尋找n最大的：
- 如果
m <= n，我們就完成了。
當m顯著超過n：成本O(m * log(n))。
形成一個二進制優先級佇列
p[n]。插入是O(log(n))，洗掉是O(log(n))，檢查最小的是O(1)。迭代
a[]，當a[i]大于 中的最小時p[]，洗掉最小并添加a[i]。
否則簡單排序a[]與成本O(m * log(m))
uj5u.com熱心網友回復：
首先，我不會深入探討是否允許呼叫庫排序的問題。這取決于你和你的教授/老板/任務。
相反，我將深入探討你是否應該這樣做的問題。想象一下，當您的陣列中有 1 000 000 個專案時。初始排序只有O(n * log(n))復雜度，成本很高。
相反，我會這樣做：
1.取前n項
創建一個陣列，我們呼叫它output（這里會呼叫輸入input）。將前 n 個（未排序的）元素復制input到output.
2.排序輸出
是的，這是一個 nlog(n) 復雜度的演算法，但你的output演算法可能比你的input.
3. 繼續回圈
繼續從第 (n 1) 個元素開始回圈input，并將每個元素與中的最小元素進行比較output（這就是我們排序的原因output）。如果 的最小元素output大于當前元素，則在此迭代中不執行任何操作。否則，找到其中最大的元素output仍然小于當前元素，將所有較小的元素向左移動output并將當前元素放在正確的位置。
Javascript 中的示例邏輯
function(item, output) {
let highestIndex = -1;
while ((output[highestIndex 1] < item) && (highestIndex 1 < output.length)) highestIndex ;
if (highestIndex >= 0) {
for (let index = 0; index < highestIndex; index ) output[index] = output[index 1];
output[highestIndex] = item;
}
}
4.考慮邊緣情況
- 如果 n 為 0，則結??果為 0，不需要任何回圈
- 如果 n 等于 的長度
input，則只需求和input - 如果 n 為負數或大于 的長度
input，則拋出錯誤
這些邊緣情況很重要，您可以輕松提高它們的性能。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/490959.html
標籤：算法
上一篇：JavaScriptonfocusout事件洗掉了無法執行其代碼的按鈕，因為當我單擊它時焦點已洗掉
下一篇：合并串列串列