查找最近Divisable在

Question

我有N整數數組爲every index i其中N<= 10^6我一定要找到我這樣A[j]%A[i]==0 0<j<i

例

3 4 2 6 7 3 

Nearest Neighbor array 
-1 -1 1 -1 -1 3 

As for last element i.e 3 6%3==0 and index of 6 is 3 so ans is 3 
similar for 2 nearest neighbor is 4 

蠻力最接近的左鄰的數組方法

int[] Neg = new int[n]; 
Arrays.fill(Neg,-1); 
for(int i=1;i<n;i++) 
for(int j=i-1;j>=0;j--) 
    if(A[j]%A[i]==0){ 
    Neg[i]=j; 
    break; 
} 

This O(n^2) approach and will fail我怎麼能想出更好的辦法可能是O（nlogn）

Answer 1

有一個簡單的O（n.sqrt（n））的算法如下：

Initialize an array D to all -1. 
For i = 1,2,...,n 
    Let a = A[i] 
    Output D[a] 
    For each divisor d of A[i]: 
     set D[d] = i 

你可以找到所有的除數O（sqrt（n））中一個簡單循環的數字，或者您可能會發現它對分析的預計算更快。

該算法通過使用D [x]來存儲作爲x的倍數的最近的數字A [j]的位置j。