如何在排序的MxN矩阵中找到第K个最小和

Question

我已经看到了如何在排序矩阵中找到第K个最小元素的解决方案，并且我也看到了如何在两个数组中找到第K个最小和的解决方案。

但是最近我发现一个问题，要求在排序的MxN矩阵中找到第K个最小和。总和必须由每一行中的一个元素组成。我真的在努力开发接近于可行解决方案的任何东西，更不用说暴力解决方案了。任何帮助将不胜感激！

我以为这会是某种堆问题...但是也许这是图形问题？我对图形不是很好。

Answer 1

您可以创建一个minHeap优先级队列，并在其中保存总和和相应的行索引。然后，一旦弹出到目前为止的最小和，您就可以通过将每行的索引加一来检查最小和的下一个候选。这是您需要的数据结构。

typedef pair<int,vector<int>> pi;
priority_queue<pi,vector<pi>,greater<pi>> pq;

您现在可以尝试问题，为获得帮助，我还添加了我为该问题编写的代码。

typedef pair<int,vector<int>> pi;

int kthSmallest(vector<vector<int>>& mat, int k) {
    int m=mat.size();
    int n=mat[0].size();
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    int sum=0;
    for(int i=0;i<m;i++)
        sum+=mat[i][0];
    vector<int> v;
    for(int i=0;i<m;i++)
        v.push_back(0);
    pq.push({sum,v});
    int count=1;
    int ans=sum;
    unordered_map<string,int> meep;
    string s;
    for(int i=0;i<m;i++)
        s+="0";
    meep[s]=1;
    while(count<=k)
    {
        ans=pq.top().first;
        v=pq.top().second;
        // cout<<ans<<endl;
        // for(int i=0;i<v.size();i++)
        //     cout<<v[i]<<" ";
        // cout<<endl;
        pq.pop();
        for(int i=0;i<m;i++)
        {
            vector<int> temp;
            sum=0;
            int flag=0;
            string luuul;
            for(int j=0;j<m;j++)
            {
                if(i==j&&v[j]<n-1)
                {
                    sum+=mat[j][v[j]+1];
                    temp.push_back(v[j]+1);
                    luuul+=to_string(v[j]+1);
                }
                else if(i==j&&v[j]==n-1)
                {
                    flag=1;
                    break;
                }
                else
                {
                    sum+=mat[j][v[j]];
                    temp.push_back(v[j]);
                    luuul+=to_string(v[j]);
                }
            }
            if(!flag)
            {
                if(meep[luuul]==0)
                    pq.push({sum,temp});
                meep[luuul]=1;
            }
        }
        // cout<<endl;
        count++;
    }
    return ans;
}