Tìm tổng nhỏ nhất thứ K của ma trận với các hàng được sắp xếp trong C ++

Giả sử chúng ta có một ma trận m * n được gọi là mat và một số nguyên k, mat có các hàng được sắp xếp theo thứ tự không giảm. Chúng ta có thể chọn chính xác một phần tử từ mỗi hàng để tạo thành một mảng. Chúng ta phải tìm tổng mảng nhỏ nhất thứ K trong số tất cả các mảng có thể có.

Vì vậy, nếu đầu vào giống như mat =[[1,3,11], [2,4,6]]

và k =5, thì đầu ra sẽ là 7, như khi chúng ta chọn một phần tử từ mỗi hàng, k tổng nhỏ nhất đầu tiên là [1,2], [1,4], [3,2], [3,4] , [1,6]. ở đây tổng thứ 5 là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàng đợi ưu tiên pq

• Xác định một mảng 2D m

• Xác định một hàm update (), nó sẽ lấy một mảng v, i, ok, khởi tạo nó bằng false,

• nếu tôi giống với kích thước của v, thì -

  • nếu ok là false thì -

    • trở lại

  • trở lại

  • để khởi tạo j:=0, khi j

    • sum:=sum + m [j, v [j]]

  • Xác định tạm thời mảng và sao chép v vào đó

  • chèn tổng vào tạm thời ở đầu

  • chèn tạm thời vào pq

  • trở lại

• (tăng v [i] lên 1)

• nếu ok là false và v [i]

  • cập nhật (v, i + 1, true)

• cập nhật (v, i + 1, true)

• cập nhật (v, i + 1, ok)

• Từ phương thức chính, hãy làm như sau -

• m:+ ma trận cho trước

• ret:=0

• n:=số hàng của m

• z:=số cột của m

• để khởi tạo i:=0, khi i

  • ret:=ret + m [i, 0]

• Xác định tạm thời mảng có kích thước n

• chèn ret vào tạm thời ở đầu

• chèn tạm thời vào pq

• Xác định một bộ s

• trong khi k khác 0, giảm k đi 1 trong mỗi lần lặp, thực hiện -

  • Xác định một mảng temp =top of pq

  • xóa phần tử khỏi pq

  • chèn tạm thời vào s

  • ret:=temp [0]

  • xóa phần tử tạm thời đầu tiên khỏi tạm thời

  • cập nhật (tạm thời, 0)

  • while (không phải pq trống và phần tử trên cùng của pq là thành viên của s), do -

    • xóa phần tử khỏi pq

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

7