給定一個整數n和陣列a，我需要找到每個i， 1≤ i ≤ n，左邊有多少個元素小于或等于a i
例子：
5
1 2 1 1 2
輸出
0 1 1 2 4
我可以在 O( N 2 ) 中做到這一點，但我想問是否有任何方法可以更快地做到這一點，因為N非常大（N ≤ 10 6）？
uj5u.com熱心網友回復：
您可以使用分段樹，您只需要使用稱為范圍樹的修改版本。范圍樹允許矩形查詢，因此您可以將維度設為索引和值，并詢問“什么值大于 x，索引介于 1 和 n 之間？” 假設某些常見的優化，查詢可以在 O(log n) 中完成。
無論哪種方式，O(N^2) 在 N < 10^6 時都完全沒問題。
uj5u.com熱心網友回復：
是的，與 O(N^2) 即 O(NlogN) 相比，它可以以更好的時間復雜度完成。我們可以使用分治演算法和樹的概念。
想看上面提到的兩種演算法的原始碼？？？ 訪問這里。
我認為 O(N^2) 應該是最壞的情況。在這種情況下，我們必須至少遍歷陣列兩次。我嘗試過 O(N^2)：
import java.io.*;
import java.lang.*;
public class GFG {
public static void main (String[] args) {
int a[]={1,2,1,1,2};
int i=0;
int count=0;
int b[]=new int[a.length];
for(i=0;i<a.length;i )
{
for(int c=0;c<i;c )
{
if(a[i]>=a[c])
{
count ;
}
}
b[i]=count;
count=0;
}
for(int j=0;j<b.length;j )
System.out.print(b[j] " ");
}`
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415947.html
標籤：