विचार करें कि हमारे पास एक कतार (queue) में खड़े लोगों की एक यादृच्छिक सूची है। यदि प्रत्येक व्यक्ति को पूर्णांकों के एक जोड़े (h, k) द्वारा वर्णित किया जाता है, जहां h ऊंचाई है और k उसके सामने उन लोगों की संख्या है जिनकी ऊंचाई h से अधिक या बराबर है। हमें कतार को पुनर्निर्मित करने के लिए एक विधि परिभाषित करनी है। इसलिए यदि दी गई सरणी [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] जैसी है, तो आउटपुट [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- दिए गए सरणी को निम्नलिखित तुलना रणनीति के आधार पर क्रमबद्ध करें
- यदि a[0] = b[0], तो a[1] > b[1] लौटाएं, अन्यथा a[0] < b[0] लौटाएं
- ans नामक एक वेक्टर बनाएं
- i को दी गई सरणी के आकार से 0 तक नीचे की ओर
- (ans के पहले तत्व + p[i, 1], p[i]) को ans सरणी में सम्मिलित करें
- ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } bool cmp(vector <int> a, vector <int> b){ if(a[0] == b[0])return a[1] > b[1]; return a[0] < b[0]; } class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int>>& p) { sort(p.begin(), p.end(), cmp); vector < vector <int> > ans; for(int i = p.size()-1; i>=0; i--){ ans.insert(ans.begin() + p[i][1], p[i]); } return ans; } }; main(){ Solution ob; vector<vector<int>> v = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}}; print_vector(ob.reconstructQueue(v)); }इनपुट
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
आउटपुट
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]