在数组中找到最接近可被整除的数

Question

我有一个包含N个整数的数组，其中N<= 10^6。对于每个索引 i ，我需要找到最近的左邻居j，使得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;
}

这种 O(n^2) 的方法很容易失败，我该如何提出更好的方法，比如O(nlogn)的算法？

- Sunny

---

数组元素的最大可能值是多少？ - dreamzor

你的“整数数组”中的值有限制吗？或者说整数范围为-2^31.. 2^31 - 1。 - Aivean

@Aivean 值的范围在1到10^6之间。 - Sunny

@dreamzor 这是 10^6。 - Sunny

你说过 N <= 10^6。但是 A[i] 呢？它是否真的满足 1 <= A[i] <= 10^6？如果是这样，将这个信息添加到问题中会更有帮助。 - user3386109

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]来存储最近的数A[j]的位置j，而A[j]是x的倍数。

- Peter de Rivaz

---

如果 A[j]%A[i]==k，其中 k 是常数，那会怎样？ - Sunny

修改算法以计算A[i]-k的因数。 - Peter de Rivaz