狐的傳說
2022-12-18 16:16:49
所以這是給出的問題。給定一個整數數組,返回一個新數組,其中新數組中的每個元素都是原始輸入數組中該元素右側較小元素的數量。例如,給定數組 [3, 4, 9, 6, 1],返回 [1, 1, 2, 1, 0],因為:There is 1 smaller element to the right of 3There is 1 smaller element to the right of 4There are 2 smaller elements to the right of 9There is 1 smaller element to the right of 6There are no smaller elements to the right of 1我想出了這個雙指針算法。 function lessThan(arr) { let results = []; let i = 0; let j = arr.length - 1; let count = 0; while (i < arr.length) { if (arr[i] > arr[j]) { count++; } j--; if (j === 1) { results.push(count); count = 0; i++; j = arr.length - 1; } } return results;}指針“i”將從開頭開始,“j”將從結尾開始。如果'j'等于1.'i'遞增并且'j'重置為末尾。這一直持續到'i'到達數組的末尾。(當'i'等于或大于arr.length while循環中斷)。根據我對時間復雜度的了解。我猜我們只遍歷數組一次是 O(n)。但是我們不應該考慮這樣一個事實,即在我們進行的過程中對“j”進行了“n”次比較嗎?我是競爭性編程和大 O 符號的新手。請幫助我。
2 回答

PIPIONE
TA貢獻1829條經驗 獲得超9個贊
它是O(n2)i
,你每次迭代都會遞增len(arr)
,直到i
reach len(arr)
。
len(arr) * len(arr)
這在即O(n2)中給出了復雜性。

UYOU
TA貢獻1878條經驗 獲得超4個贊
您可以將代碼重新排列為
function lessThan(arr) {
let results = [];
let i = 0;
while (i < arr.length) {
let j = arr.length - 1;
let count = 0;
while (j !== 1) {
if (arr[i] > arr[j]) {
count++;
}
j--;
}
results.push(count);
i++;
}
return results;
}
是的,您巧妙地將嵌套循環合并為一個循環,但這并沒有改變它的復雜性。請注意,在您的版本中,while循環運行arr.length 2次數i不是在每次迭代時遞增,而是僅在j == 1.
從我的更新版本中,不僅可以清楚地看到代碼是O(n2),而且它是錯誤的:j !== 1(or j > 1) 應該比較i而不是1- 你只想計算右邊的元素。
添加回答
舉報
0/150
提交
取消