arrays - 找到具有最小乘积的三个项目的 K 组合

Question

在解决问题时，我遇到了一种情况，我必须从给定的正数数组中找到三项组合的前 k 个乘积，这样乘积应该是最小的。给定数组 A , 大小为 n , 找到拳头 k具有最小值的三个不同数组项的乘积有效。让我们称之为MP这样

MP[i] = A[j]* A[l]*A[m] 

哪里i<K, j!=l!=m和 k<n

我当时尝试的是获取所有可能的产品，然后对它们进行排序以获得前 k 个产品。但我知道这不是高效的，因为首先 O(N^3) 用于查找所有组合产品，然后至少 O(NlogN) 用于排序 N^3 组合。所以在我的例子中数组大小并不大，但我想知道如何更有效地解决同样的问题。

Answer 1

其他解决方案的问题是它们的贪婪选择不是最优的。

一个简单的基于优先级队列的解决方案将为该问题提供最佳解决方案。 min_product 是提供所需数组的函数， map 用于跟踪已经看到的元组。我使用了一个简单的 STL 优先级队列。

//// Asume the vector a(size>=3) is sorted    
std::vector<int> a;
struct triplet{
    int i,j,k;
};

long long value(triplet& p1){
    return (long long)a[p1.i]*(long long)a[p1.j]*a[p1.k];
}

struct CompareTriplet {
    bool operator()(triplet const & p1, triplet const & p2) {
        return value(p1) > value(p2);
    }
};

void push_heap(std::priority_queue<triplet, std::vector<triplet> pq, CompareTriplet>& pq,triplet &t,std::vector<triplet>& m;){
    if (m.find(t)!=m.end()){
        m[t]=1;
        pq.push(t);
    }
}

std::vector<long long> min_product(int k){

    sort(a.begin(), a.end()); // sort if not sorted.
    int n=a.size();

    std::unodered_map<triplet,bool> m;
    std::vector<long long> MP(k);

    std::priority_queue<triplet, std::vector<triplet>, CompareTriplet> pq;

    push_heap(pq,triplet{0,1,2},m);

    for(int i=0; !pq.empty() and i<k;i++){
        auto tp = pq.top(); pq.pop();
        MP[i]=value(tp);

        if (tp.i+1<tp.j){
            push_heap(pq,triplet{tp.i+1,tp.j,tp.k},m);
        }
        if (tp.j+1<tp.k){
            push_heap(pq,triplet{tp.i,tp.j+1,tp.k},m);
        }
        if (tp.k+1<n){
            push_heap(pq,triplet{tp.i,tp.j,tp.k+1},m);
        }
    }
    return MP
}

复杂度:

如果数组没有排序，那么让它排序就是这里的瓶颈。其实在任何时候，我们都需要 top i (

对于已排序的给定数组。

由于堆中最多可以有 2*k 个元素，并且为获取 MP 的每个元素完成了 O(k) 次操作(堆和映射)。因此，运行时间复杂度为 O( k*log(k) )。

是的，它独立于 n。