मान लीजिए कि हमारे पास एक सरणी A है, हमें इसे दो उप-सरणी में बाएँ और दाएँ विभाजित करना है जैसे कि -
-
बाएँ उप-सरणी में प्रत्येक तत्व दाएँ उप-सरणी में प्रत्येक तत्व से कम या उसके बराबर है।
-
बाएँ और दाएँ उप-सरणी खाली नहीं हैं।
-
लेफ्ट सबअरे का आकार सबसे छोटा संभव है।
हमें इस तरह के विभाजन के बाद बाईं ओर की लंबाई का पता लगाना होगा। यह गारंटी है कि ऐसा विभाजन मौजूद है।
तो अगर इनपुट [5,0,3,8,6] जैसा है, तो आउटपुट 3 होगा, क्योंकि लेफ्ट एरे [5,0,3] होगा और राइट सबरे [8,6] होगा। पी>
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=A का आकार, अधिकतम n आकार की एक सरणी बनाएं
-
minVal :=A का अंतिम तत्व
-
मैक्सएक्स [0]:=ए [0]
-
मैं के लिए 1 से n - 1 की सीमा में
-
maxx[i] :=अधिकतम A[i] और A[i – 1]
-
-
उत्तर :=A का आकार – 1
-
मेरे लिए n - 1 से नीचे 1 तक की श्रेणी में है
-
minVal :=न्यूनतम minVal और A[i]
-
यदि minVal>=max[i – 1], तो उत्तर :=i
-
-
वापसी उत्तर
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int partitionDisjoint(vector <int>& A) {
int n = A.size();
vector <int> maxx(n);
int minVal = A[n - 1];
maxx[0] = A[0];
for(int i = 1; i < n; i++){
maxx[i] = max(A[i], maxx[i - 1]);
}
int ans = A.size() - 1;
for(int i = n - 1; i >= 1; i--){
minVal = min(minVal, A[i]);
if(minVal >= maxx[i - 1]){
ans = i;
}
}
return ans;
}
};
main(){
vector<int> v1 = {5,0,3,8,6};
Solution ob;
cout << (ob.partitionDisjoint(v1));
} इनपुट
[5,0,3,8,6]
आउटपुट
3