C++ में सॉर्टेड पंक्तियों वाले मैट्रिक्स का Kवां सबसे छोटा योग

समस्या विवरण

मान लीजिए हमारे पास एक 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]। यहां 5वां योग 7 है।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (प्रायोरिटी क्यू + बैकट्रैकिंग):

• एक प्रायोरिटी क्यू pq परिभाषित करें
• एक 2D सरणी m परिभाषित करें
• update() नामक एक फ़ंक्शन परिभाषित करें, जो एक सरणी v, i, ok (false से आरंभ) लेता है:
  • यदि i, v के आकार के समान है:
    • यदि ok false है, तो लौटें
    • वापस लौटें
  • j := 0 से आरंभ करें, जब j < v का आकार, j को 1 से बढ़ाते हुए:
    • sum := sum + m[j][v[j]]
  • एक सरणी temp परिभाषित करें और v को इसमें कॉपी करें
  • sum को temp की शुरुआत में डालें
  • temp को pq में डालें
  • वापस लौटें
• v[i] को 1 से बढ़ाएं
• यदि ok false है और v[i] < z:
  • update(v, i + 1, true)
• update(v, i + 1, true)
• update(v, i + 1, ok)
• मुख्य विधि से निम्नलिखित करें:
  • m := दी गई मैट्रिक्स
  • ret := 0
  • n := m की पंक्ति संख्या
  • z := m की स्तंभ संख्या
  • i := 0 से आरंभ करें, जब i < n, i को 1 से बढ़ाते हुए:
    • ret := ret + m[i][0]
  • आकार n की एक सरणी temp परिभाषित करें
  • ret को temp की शुरुआत में डालें
  • temp को pq में डालें
  • एक सेट s परिभाषित करें
  • जब k शून्येतर है, प्रत्येक पुनरावृत्ति में k को 1 से घटाते हुए:
    • temp := pq का शीर्ष तत्व
    • pq से तत्व हटाएं
    • temp को s में डालें
    • ret := temp[0]
    • temp से पहला तत्व हटाएं
    • update(temp, 0)
    • जब (pq खाली नहीं है और pq का शीर्ष तत्व s का सदस्य है):
      • pq से तत्व हटाएं
  • ret लौटाएं

C++ कार्यान्वयन

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

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,3,11},{2,4,6}};
    cout << (ob.kthSmallest(v, 5));
    return 0;
}

इनपुट

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

आउटपुट

7