找到包含 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

不确定最快。

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

所以，（下面太复杂了，看）
(〇• 如果 k ≤ n
• 将 minProduct 初始化为 a[0]*a[k+1])

保持两个dynamic minmax data structuresupToI和beyondIplusK
从 { } 和 { a[j] 开始 | k≤j}
对于每个 i 从 0 到 n - k - 1
- 添加一个[i]到upToI
- 从 beyondIplusK
- 在
  中检查新的最小产品 min(upToI)×min(beyondIplusK),min(upToI)×max(beyondIplusK),
  max(upToI)×min(beyondIplusK) 和 max(upToI)×max(beyondIplusK)

Answer 2

对于"minimum magnitude"

找到 2 个 "smallest magnitude" 元素，然后（在找到两个零或搜索整个数组之后）将它们相乘。

对于 "lowest value" 没有 abs(i - j) > k 部分

有3种可能：

两个最高（最小量级）的负数
两个最低（最小量级）的非负数
最低（最大幅度）负数和最高（最大幅度）非负数

您可以搜索所有 6 个值并找出产品以及最后哪个最好。

但是；一旦看到零，您就知道您不需要再了解前两种可能性；一旦你看到一个负数和一个非负数，你就知道你只关心第三种可能性。

这导致了具有 3 个状态的有限状态机 - "care about all 3 possibilities"、"answer is zero unless a negative number is seen" 和 "only care about the last possibility"。这可以实现为一组 3 个循环，其中 2 个循环在（有限状态机的）状态发生变化时跳入 (goto) 另一个循环的中间。

具体来说，它可能看起来有点像（未经测试）：

   // It could be any possibility

   for(ll i=0;i<n;i++) {
       if(a[i] >= 0) {
            if(a[i] < lowestNonNegative1) {
                lowestNonNegative2 = lowestNonNegative1;
                lowestNonNegative1 = a[i];
            }
            if(lowestNonNegative2 == 0) {
                goto state2;
            }
       } else {
            if(a[i] > highestNegative1) {
                highestNegative2 = highestNegative1;
                highestNegative1= a[i];
            }
            if(lowestNonNegative1 < LONG_MAX) {
                goto state3;
            }
       }
   }
   if(lowestNonNegative2 * lowestNonNegative1 < highestNegative2 * highestNegative1) {
       cout << lowestNonNegative2 * lowestNonNegative1;
   } else {
       cout << highestNegative2 * highestNegative1;
   }
   return;

   // It will be zero, or a negative and a non-negative

   for(ll i=0;i<n;i++) {
state2:
       if(a[i] < 0) {
           goto state3;
       }
   }
   cout << "0";
   return;

   // It will be a negative and a non-negative

   for(ll i=0;i<n;i++) {
state3:
       if(a[i] < lowestNegative) {
           lowestNegative = a[i];
       } else if(a[i] > highestNonNegative) {
           highestNonNegative = a[i];
       }
    }
    cout << lowestNegative * highestNonNegative;
    return;

对于 "lowest value" 和 abs(i - j) > k 部分

在这种情况下你还有3种可能；并且可以使它使用相同的“有限状态机 3 循环”方法工作，但它变得太 messy/ugly。对于这种情况，更好的选择可能是预扫描数组以确定是否有任何零以及它们是全负还是全正；这样在预扫描之后你就可以知道答案是零或者 select 一个专门为特定可能性设计的循环。

Answer 3

假设至少有一对元素满足条件并且其中两个元素相乘没有溢出，这可以在Theta(n-k)时间完成，最差Theta(1)space - 最好的情况是，像这样：

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;

就时间和 space 的渐近最坏情况复杂度而言，这是最佳的，因为最佳产品可能是 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 的索引。我们也需要遍历所有这些，但这是不必要的，因为固定 i 处 j 的 a[i+k+1]*a[j] 的最小值由于单调性而等于 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]}，它在 i 的每次迭代中仅增长一个元素 (a[i]) ，我们可以简单地跟踪 max(a[j]) 和 min(a[j]) 的单个变量，如果 a[i] 大于或小于先前的最优值，则更新它们。这是通过代码示例中的 back_max 和 back_min 完成的。

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

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

Fastest way to find minimal product of 2 array elements containing 200000+ elements

c++

algorithm

optimization

minimum