問題如下：
令 P 是一個正整數陣列。我需要根據這個定義創建一個陣列 S：
S[i] 包含小于或等于 P[i] 的元素數。
這必須在線性時間內實作 - O(n)。
示例：如果 P=[2,7,4,5,9,12]，則 S=[0,1,0,1,4,5]。
那是因為 P[0] 有零個元素小于或等于它（最多 P[0]），所以 S[0]=0，而 P[1] 只有 P[0] 比它小（最多 P[ 1])，所以 S[1]=1，依此類推。
這是我的嘗試（在 Java 中）：
我的嘗試是對陣列進行一次傳遞，并利用堆疊將先前的索引存盤在 P 中。遺憾的是，這是一次失敗的嘗試，因為對于輸入 P=[17,4,2,0,15] 輸出是不正確的。
這是我寫的代碼：
public static int[] build_s(int[] p) {
IntegerStack temp = new IntegerStack(p.length);
temp.push(0);
int[] s = new int[p.length];
int max = p[0];
for (int i = 0; i < p.length; i ) {
if (p[i] >= max) {
s[i] = i 1;
max = p[i];
} else if (p[i-1] > p[i]) {
if (p[i] > temp.peek())
temp.push(i);
s[i] = 1;
} else {
s[i] = (i - temp.peek());
}
}
return s;
}
我真的很感激能幫助我的演算法正常作業。我可以看到問題出現在有諸如 4,2,0,15 這樣的序列破壞演算法時，但我無法在 O(n) 時間內找出解決方案。
謝謝！
uj5u.com熱心網友回復：
在線性時間復雜度中，即O(n)不可能找到當前位置左側存在的小于或等于它的元素的計數。
讓我們假設這樣的演算法存在O(N)時間復雜度。然后通過使用這個“演算法”的結果，在原始給定陣列中應用一次，然后將其反轉一次，我們可以及時找到已排序的陣列O(N)。
現在我們知道，即使在最好的情況下，對由隨機整陣列成的陣列進行排序的時間復雜度也是O(N*logN)。
因此，我們的假設是錯誤的，這樣的演算法不存在。
uj5u.com熱心網友回復：
解決此問題的一種方法O(nlog(n))是使用Fenwick/BIT. 但是BIT構造空間需要一個陣列，size其maximum值等于陣列中的值（前提是陣列中的所有元素都是正數）。BIT陣列的構造是O(size)。對于陣列中的每個元素，您需要將其1作為值插入到BIT陣列中，對小于當前元素的元素數量的每個查詢都將是O(log(size)). 所以總時間復雜度為O(sizelog(size)). 這size是BIT陣列的長度。你可以在這里了解更多BIT
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/378275.html
上一篇：springboot和feign中是否有任何示例源代碼可用于直接呼叫docusigneSignatureRESTAPI而不使用SDK？