給定一個包含至少 5 個專案的陣列 N，我想找到 2 個數字（P 和 Q），其中 0 < P < Q < N - 1。
假設我們有以下陣列：
const N = [1, 9, 4, 5, 8];
- 如果 P = 1 , Q = 2 ，則成本將為 N[P] N[Q] = N[1] N[2] = 9 4 = 13
- 如果 P = 1, Q = 3 ，則成本將為 N[P] N[Q] = N[1] N[3] = 9 5 = 14
- 如果 P = 2, Q = 3 ，則成本將為 N[P] N[Q] = N[2] N[3] = 4 5 = 9
從這里給出最小成本的組合是P = 2和Q = 3。
這是我找到的解決方案，如果我能提高它的時間復雜度，我正在尋求你的幫助：
function solution(N) {
// since 0 < P < Q < N - 1
const sliced = N.slice(1, N.length - 1);
const sorted = sliced.sort((a, b) => a - b);
// the minimum should be from the start since we have sorted the array
const P = 0;
const Q = 1;
return getCost(P, Q, sorted);
}
function getCost(P, Q, N) {
return N[P] N[Q];
}
// output should be 9
console.log(solution([1, 9, 4, 5, 8]))
在最好的情況下，由于排序，它是0(n log(n))，但我想知道我們是否可以將其改進為 O(n)。
謝謝你的幫助
uj5u.com熱心網友回復：
function twoSmallest(arr) {
let [first, second] = [arr[1], arr[2]]
for (let i = 3; i < arr.length - 1; i ) {
const el = arr[i]
if (el < first && el < second) {
[first, second] = [Math.min(first, second), el]
} else if (el < first) {
[first, second] = [second, el]
} else if (el < second) {
second = el
}
}
return first second
}
這是一個O(n)時間和O(1)空間的解決方案。它還確保保留具有較小索引的元素，first以防您需要使用索引并且出于某種原因感興趣。
演算法很清楚，IMO，但 JS 代碼可能不是最好的實作。好久沒寫JS了。
uj5u.com熱心網友回復：
你覺得這個解決方案怎么樣？
function solution([_, ...n]) {
n.pop()
n.sort((a, b) => a - b);
return n[0] n[1];
}
// output should be 9
console.log(solution([1, 9, 4, 5, 8]))邏輯與您概述的邏輯相同 - 僅使用 JS 提供的其他方法。
uj5u.com熱心網友回復：
我很確定這是 O(n)：
const solution = (arr) => {
// find smallest that's not at either end
let idx = 1;
let P = arr[1];
for(let i = 2; i < arr.length-1; i ) {
if(arr[i] < P) {
idx = i;
P = arr[i];
}
}
// find second smallest that's not at either end
let Q = Infinity;
for(let i = 1; i < arr.length-1; i ) {
if(i == idx) continue;
if(arr[i] < Q) Q = arr[i];
}
return P Q;
}
uj5u.com熱心網友回復：
這是使用 Python 在串列中找到 k 個最小數字的最快方法。其余的都是微不足道的
在python中獲取大小為N的未排序串列中的k個最小數字的最快方法？
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/420776.html
標籤：