array-algorithms - 数组中的最大元素等于数组中两个元素的乘积

Question

我们需要在数组中找到最大元素，该元素也等于同一数组中两个元素的乘积。例如 [2,3,6,8] ，这里 6=2*3 所以答案是 6。

我的方法是对数组进行排序，然后使用双指针方法检查每个元素是否存在乘积。这是 o(nlog(n)) + O(n^2) = O(n^2) 方法。有没有更快的方法？

Answer 1

如果允许在 A[i] 中使用 O(M) 内存 M = 最大数量，则 O(n * sqrt(n)) 有一个稍微更好的解决方案
使用大小为 M 的数组来标记每个数字，同时将它们从小到大遍历。
对于每个数字，尝试它的所有因子，看看它们是否已经存在于数组映射中。

这是一个伪代码:

#define M 1000000
int array_map[M+2];
int ans = -1;
sort(A,A+n);
for(i=0;i<n;i++) {
  for(j=1;j<=sqrt(A[i]);j++) {
    int num1 = j;
    if(A[i]%num1==0) {
      int num2 = A[i]/num1;
      if(array_map[num1] && array_map[num2]) {
        if(num1==num2) {
            if(array_map[num1]>=2) ans = A[i];
        } else {
          ans = A[i];
        }
      }
    }
  }
  array_map[A[i]]++;
}

如果您知道如何在 log(M) 中找到所有可能的因素，则有一种更好的方法，这将变为 O(n*logM)。您必须为此使用筛选和回溯