C++ में सॉर्ट की गई पंक्तियों के साथ मैट्रिक्स का Kth सबसे छोटा योग ज्ञात करें

मान लीजिए कि हमारे पास एक m * n मैट्रिक्स है जिसे 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

• फ़ंक्शन अपडेट को परिभाषित करें (), यह एक सरणी v लेगा, i, ठीक है इसे गलत के साथ प्रारंभ करें,

• यदि i, v के आकार के समान है, तो -

  • अगर ठीक गलत है, तो -

    • वापसी

  • वापसी

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • योग:=योग + एम [जे, वी [जे]]

  • एक सरणी अस्थायी परिभाषित करें और उसमें v कॉपी करें

  • शुरुआत में अस्थायी में योग डालें

  • pq में अस्थायी डालें

  • वापसी

• (v[i] 1 से बढ़ाएं)

• यदि ठीक गलत है और v[i]

  • अपडेट (v, i + 1, सच)

• अपडेट (v, i + 1, सच)

• अपडेट (v, i + 1, ओके)

• मुख्य विधि से निम्न कार्य करें -

• मी :+ दिया गया मैट्रिक्स

• रिट:=0

• n :=मी की पंक्ति गणना

• z :=मी की कॉलम संख्या

• इनिशियलाइज़ i :=0 के लिए, जब i

  • रिट:=रिट + एम[i, 0]

• आकार n की एक सरणी अस्थायी परिभाषित करें

• शुरुआत में अस्थायी में रिट डालें

• pq में अस्थायी डालें

• एक सेट को परिभाषित करें

• जबकि k गैर-शून्य है, प्रत्येक पुनरावृत्ति में k को 1 से घटाएं, −

  . करें

  • एक सरणी अस्थायी परिभाषित करें =pq के ऊपर

  • pq से तत्व हटाएं

  • s में अस्थायी डालें

  • रिट:=अस्थायी [0]

  • अस्थायी से अस्थायी का पहला तत्व हटाएं

  • अपडेट (अस्थायी, 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}}

आउटपुट

7