查找最近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。