用C ++查找带排序行的矩阵的Kth最小和

假设我们有一个m * n矩阵，称为mat，一个整数k，mat的行以非降序排列。我们可以从每一行中精确选择一个元素来形成一个数组。我们必须在所有可能的数组中找到第K个最小的数组和。

因此，如果输入像mat = [[1,3,11]，[2,4,6]]

并且k = 5，则输出将为7，因为当我们从每行中选择一个元素时，前k个最小的和为[1,2]，[1,4]，[3,2]，[3,4] ，[1,6]。第五个总和是7。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个优先级队列pq

• 定义一个2D数组m

• 定义一个函数update()，它将使用数组v，i，好的，用false初始化它，

• 如果i与v的大小相同，则-

• sum：= sum + m [j，v [j]]

• 返回

• 如果ok为假，则-

• 返回

• 对于初始化j：= 0，当j <v的大小时，更新（将j增加1），执行-

• 定义一个数组临时并将v复制到其中

• 在开始时将sum插入temp

• 将温度插入pq

• 返回

• （将v [i]增加1）

• 如果ok为假且v [i] <z，则-

• 更新（v，i + 1，true）

• 更新（v，i + 1，true）

• 更新（v，i + 1，ok）

• 从主要方法中执行以下操作-

• m：+给定矩阵

• ret：= 0

• n：= m的行数

• z：= m的列数

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• ret：= ret + m [i，0]

• 定义大小为n的数组温度

• 在开始时将ret插入temp

• 将温度插入pq

• 定义一组

• 当k为非零值时，请在每次迭代中将k减1，然后执行-

• 从pq中删除元素

• 定义一个数组temp = pq的顶部

• 从pq中删除元素

• 将temp插入s

• ret：= temp [0]

• 从temp中删除temp的第一个元素

• 更新（温度，0）

• 而（不是pq为空，并且pq的顶部元素是s的成员），则执行-

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
struct Cmp{
   bool operator()(vector <int>& a, vector <int>& b) {
      return !(a[0] < b[0]);
   }
};
class Solution {
   public:
   priority_queue<vector<int>, vector<vector<int> >, Cmp> pq;
   vector<vector<int> > m;
   int z;
   void update(vector<int>& v, int i, bool ok = false){
      if (i == v.size()) {
         if (!ok)
         return;
         int sum = 0;
         for (int j = 0; j < v.size(); j++) {
            sum += m[j][v[j]];
         }
         vector<int> temp(v.begin(), v.end());
         temp.insert(temp.begin(), sum);
         pq.push(temp);
         return;
      }
      v[i]++;
      if (!ok && v[i] < z)
      update(v, i + 1, true);
      v[i]--;
      update(v, i + 1, ok);
   }
   int kthSmallest(vector<vector<int> >& m, int k){
      this->m = m;
      int ret = 0;
      int n = m.size();
      z = m[0].size();
      for (int i = 0; i < n; i++) {
         ret += m[i][0];
      }
      vector<int> temp(n);
      temp.insert(temp.begin(), ret);
      pq.push(temp);
      set<vector<int> > s;
      while (k--) {
         vector<int> temp = pq.top();
         pq.pop();
         s.insert(temp);
         ret = temp[0];
         temp.erase(temp.begin());
         update(temp, 0);
         while (!pq.empty() && s.count(pq.top())) {
            pq.pop();
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,3,11},{2,4,6}};
   cout << (ob.kthSmallest(v, 5));
}

输入项

{{1,3,11},{2,4,6}}

输出结果

7