找到包含 200000+ 个元素的 2 个数组元素的最小乘积的最快方法

Question

我有一个数组a[n]。号码n是我们输入的。我需要找到的最小的产品a[i]和a[j]如果：

1) abs(i - j) > k

2)a[i] * a[j]最小化

这是我的解决方案（非常幼稚）：

#include <iostream>
using namespace std;
#define ll long long
int main() {
    ll n,k; cin >> n >> k;

    ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];

    ll mn; bool first = true;

    for(ll i=0;i<n;i++) {
        for(ll j=0;j<n;j++) {
            if(i!=j)
            if(abs(i-j) > k) {
                if(first) {
                    mn = a[i]*a[j];
                    first = false;
                } else if(a[i]*a[j] < mn) mn = a[i]*a[j];
            }
        }
    }
    cout << mn << endl;
}

但是我想知道是否有任何更快的方法可以找到具有距离的最小乘积？

Answer 1

假设至少有一对元素满足条件并且其中两个元素的乘法没有溢出，这可以在Theta(n-k)时间和Theta(1)空间最坏和最好的情况下完成，如下所示：

auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];

for(std::size_t i=1; i<n-(k+1); ++i) {
    back_max = std::max(back_max, a[i]);
    back_min = std::min(back_min, a[i]);
    best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}

return best;

就时间和空间的渐近最坏情况复杂度而言，这是最佳的，因为最佳乘积可能a[0]与n-(k+1)距离至少为 的任何元素有关k+1，因此n-(k+1)任何解决问题的算法至少需要读取整数。

该算法背后的思想如下：

最佳产品使用 的两个元素a，假设它们是a[r]和a[s]。不失一般性，我们可以假设，s > r因为乘积是可交换的。

由于限制，abs(s-r) > k这意味着s >= k+1. 现在s可能是满足这个条件的每个索引，所以我们迭代这些索引。这是i所示代码中的迭代，但k+1为了方便起见，它被移动了（并不重要）。对于每次迭代，我们需要找到涉及i+k+1最大索引的最优乘积，并将其与之前的最佳猜测进行比较。

由于距离要求，要配对的可能索引i+k+1都是小于或等于的索引i。我们需要遍历所有这些为好，但这是不必要的，因为至少a[i+k+1]*a[j]在j以固定i等于min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))由于该产品（取最小值相对于最小和最大的两个以上的单调性a[j]占了两个可能的a[i+k+1]单调性的两个可能方向的符号或等效的符号。）

由于a[j]我们在这里优化的一组值只是{a[0], ..., a[i]}，它a[i]在 的每次迭代中仅增加一个元素 ( ) i，因此我们可以通过更新单个变量（如果大于或小于先前的最佳值）来简单地跟踪max(a[j])和min(a[j])使用单个变量a[i]。这是用做back_max与back_min在代码示例。

迭代的第一步 ( i=0) 在循环中被跳过，而是作为变量的初始化执行。

Answer 2

不确定最快。

对于没有i < j - k的更简单问题，最小乘积是来自两个最小和最大元素的对的乘积。

所以，（下面太复杂了，看walnut 的回答）
(?•
balk if k ? n ??• 将 minProduct 初始化为 a[0]*a[k+1])

• 保持两个动态 minmax 数据结构 upToI和BeyondIplusK
  以 { } 和 { a[ j ] |开头 ķ？j }
• 对于每个i从 0 到n - k - 1
  • 将 [ i ]添加到upToI
  • 从BeyondIplusK 中删除 a[ i + k ]
  • 检查
    min( upToI )×min( BeyondIplusK )、min( upToI )×max( BeyondIplusK )、
    max( upToI )×min( BeyondIplusK ) 和 max( upToI )×max( BeyondIplusK ) 之间的新最小乘积