C++ এ সাজানো সারি সহ একটি ম্যাট্রিক্সের Kth ক্ষুদ্রতম সমষ্টি খুঁজুন

ধরুন আমাদের একটি m * n ম্যাট্রিক্স আছে যাকে বলা হয় ম্যাট, এবং একটি পূর্ণসংখ্যা k, ম্যাটের সারিগুলি কম না হওয়া ক্রমে সাজানো আছে। আমরা একটি অ্যারে তৈরি করতে প্রতিটি সারি থেকে ঠিক একটি উপাদান বেছে নিতে পারি। আমাদের সমস্ত সম্ভাব্য অ্যারের মধ্যে Kth ক্ষুদ্রতম অ্যারের যোগফল খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট ম্যাটের মত হয় =[[1,3,11],[2,4,6]]

1	3	1 1
2	4	6

এবং k =5, তাহলে আউটপুট হবে 7, যেমন আমরা যখন প্রতিটি সারি থেকে একটি উপাদান নির্বাচন করি তখন প্রথম k ক্ষুদ্রতম যোগফল হয় [1,2], [1,4], [3,2], [3,4] , [1,6]। এখানে 5ম যোগফল হল 7।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি অগ্রাধিকার সারি pq
সংজ্ঞায়িত করুন
একটি 2D অ্যারে m
সংজ্ঞায়িত করুন
একটি ফাংশন আপডেট (), এটি একটি অ্যারে নিয়ে যাবে, i, ঠিক আছে এটি মিথ্যা দিয়ে শুরু করুন,
যদি আমি v এর আকারের সমান হয়, তাহলে −
- যদি ok মিথ্যা হয়, তাহলে -
  - ফেরত
- ফেরত
- j শুরু করার জন্য :=0, যখন j করুন
  - যোগফল :=যোগফল + m[j, v[j]]
- একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন এবং এতে v কপি করুন
- শুরুতে তাপমাত্রায় যোগফল ঢোকান
- pq
  -এ তাপমাত্রা সন্নিবেশ করান
- ফেরত
(v[i] 1 দ্বারা বৃদ্ধি করুন)
যদি ok মিথ্যা হয় এবং v[i]
- আপডেট (v, i + 1, সত্য)
আপডেট (v, i + 1, সত্য)
আপডেট (v, i + 1, ঠিক আছে)
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
m :+ দেওয়া ম্যাট্রিক্স
ret :=0
n :=m এর সারি গণনা
z :=m
কলামের সংখ্যা
আরম্ভ করার জন্য i :=0, যখন i
- ret :=ret + m[i, 0]
n
আকারের একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন
শুরুতে টেম্পে ret ঢোকান
pq
-এ তাপমাত্রা সন্নিবেশ করান
একটি সেট s
সংজ্ঞায়িত করুন
যখন k অ-শূন্য, প্রতিটি পুনরাবৃত্তিতে k কে 1 দ্বারা হ্রাস করুন, −
করুন
- একটি অ্যারে temp =pq এর শীর্ষ
  সংজ্ঞায়িত করুন
- pq
  থেকে উপাদান মুছুন
- s
  -এ তাপমাত্রা সন্নিবেশ করান
- ret :=temp[0]
- temp থেকে temp-এর প্রথম উপাদান মুছুন
- আপডেট (তাপ, 0)
- যখন (pq খালি নয় এবং pq-এর উপরের উপাদানটি s-এর সদস্য), কর −
  - pq
    থেকে উপাদান মুছুন
রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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

৷