मान लीजिए हमारे पास लंबाई m और n की दो सरणियां हैं जिनमें 0-9 के अंक हैं जो दो संख्याओं को दर्शाते हैं। हमें दोनों के अंकों से लंबाई k की अधिकतम संख्या बनानी है जो m + n से कम है। हमें ध्यान रखना होगा कि एक ही सरणी के अंकों का सापेक्ष क्रम संरक्षित रहना चाहिए। हमें k अंकों की सरणी ढूंढनी है। तो यदि इनपुट [3,4,7,5] और [9,1,3,5,8,4] जैसे हैं, और k = 5, तो उत्तर [9,8,7,5,4] होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक फ़ंक्शन mergeThem() परिभाषित करें, जो एक सरणी nums1, एक सरणी nums2 लेगा,
- एक सरणी ret परिभाषित करें
- i := 0, j := 0, n := nums1 का आकार, m := nums2 का आकार
- जब (i < n या j < m), करें -
- यदि greater(nums1, nums2, i, j) को कॉल करना सत्य है, तो -
- nums1[i] को ret के अंत में डालें
- (i को 1 से बढ़ाएं)
- अन्यथा
- nums2[j] को ret के अंत में डालें
- (j को 1 से बढ़ाएं)
- यदि greater(nums1, nums2, i, j) को कॉल करना सत्य है, तो -
- ret लौटाएं
- एक फ़ंक्शन modify() परिभाषित करें, जो एक सरणी v, k लेगा,
- एक स्टैक st परिभाषित करें
- एक सरणी ret परिभाषित करें
- i := 0 से आरंभ करें, जब i < v का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें -
- x := v[i]
- जब (st खाली नहीं है और st का शीर्ष तत्व < x और st का आकार + v का आकार - i - 1 >= k), करें -
- st से तत्व हटाएं
- यदि st का आकार < k, तो -
- x को st में डालें
- जब (st खाली नहीं है), करें -
- st के शीर्ष तत्व को ret के अंत में डालें
- st से तत्व हटाएं
- सरणी ret को उल्टा करें
- ret लौटाएं
- एक फ़ंक्शन greater() परिभाषित करें, जो एक सरणी a, एक सरणी b, i, j लेगा,
- जब (i < a का आकार और j < b का आकार और a[i], b[j] के समान है), करें -
- i को 1 से बढ़ाएं और j को 1 से बढ़ाएं
- सत्य लौटाएं जब j == b का आकार या i < a का आकार और a[i] > b[j]
- मुख्य विधि से निम्नलिखित करें:
- एक सरणी ret परिभाषित करें
- n := nums1 का आकार
- m := nums2 का आकार
- i := 0 से आरंभ करें, जब i <= k, अपडेट करें (i को 1 से बढ़ाएं), करें -
- यदि i <= n और (k - i) <= m, तो -
- एक सरणी candidate = mergeThem(modify(nums1, i), modify(nums2, k - i)) परिभाषित करें
- यदि greater(candidate, ret, 0, 0) सत्य है, तो -
- ret := candidate
- यदि i <= n और (k - i) <= m, तो -
- ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> mergeThem(vector<int> nums1, vector<int> nums2) { vector<int> ret; int i = 0; int j = 0; int n = nums1.size(); int m = nums2.size(); while (i < n || j < m) { if (greater(nums1, nums2, i, j)) { ret.push_back(nums1[i]); i++; } else { ret.push_back(nums2[j]); j++; } } return ret; } vector<int> modify(vector<int>& v, int k) { stack<int> st; vector<int> ret; for (int i = 0; i < v.size(); i++) { int x = v[i]; while (!st.empty() && st.top() < x && st.size() + (v.size() - i) - 1 >= k) { st.pop(); } if (st.size() < k) st.push(x); } while (!st.empty()) { ret.push_back(st.top()); st.pop(); } reverse(ret.begin(), ret.end()); return ret; } bool greater(vector<int>& a, vector<int>& b, int i, int j) { while (i < a.size() && j < b.size() && a[i] == b[j]) i++, j++; return j == b.size() || (i < a.size() && a[i] > b[j]); } vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) { vector<int> ret; int n = nums1.size(); int m = nums2.size(); for (int i = 0; i <= k; i++) { if (i <= n && (k - i) <= m) { vector<int> candidate = mergeThem(modify(nums1, i), modify(nums2, k - i)); if (greater(candidate, ret, 0, 0)) { ret = candidate; } } } return ret; } }; main() { Solution ob; vector<int> v = { 3, 4, 7, 5 }, v1 = { 9, 1, 3, 5, 8, 4 }; print_vector(ob.maxNumber(v, v1, 5)); }इनपुट
{ 3, 4, 7, 5 } { 9, 1, 3, 5, 8, 4 } 5आउटपुट
[9, 8, 7, 5, 4, ]
