मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है, और दूसरी संख्या k, हमें यह जांचना होगा कि क्या सूची को उन सूचियों में विभाजित किया जा सकता है जहां प्रत्येक सूची में k मान हैं और मान लगातार बढ़ रहे हैं।
इसलिए, यदि इनपुट संख्या =[4, 3, 2, 4, 5, 6], के =3 की तरह है, तो आउटपुट सही होगा, क्योंकि हम सूची को [2, 3, 4] और [ में विभाजित कर सकते हैं। 4, 5, 6]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक मानचित्र परिभाषित करें
-
प्रत्येक कुंजी के लिए इसे m
. में-
m[it] को 1 से बढ़ाएं
-
-
ठीक :=सच
-
जबकि (m का आकार 0 नहीं है और ठीक सत्य है), करें -
-
ठीक :=असत्य
-
प्रत्येक की-वैल्यू पेयर के लिए इसे m
. में जोड़ें-
अगर (it.key - 1) मी में नहीं है, तो -
-
झंडा :=सच
-
इनिशियलाइज़ करने के लिए i :=it.key, जब i <=it.key + k-1, अपडेट करें (i को 1 से बढ़ाएँ), do -
-
अगर मैं मी में मौजूद नहीं है, तो -
-
झंडा :=झूठा
-
-
-
यदि ध्वज सत्य है, तो -
-
इनिशियलाइज़ करने के लिए i :=it.key , जब i <=it.key + k-1, अपडेट (iby 1 बढ़ाएँ), करें -
-
(मी [i] 1 से घटाएं)
-
यदि m[i] 0 के समान है, तो -
-
मुझे मी से मिटाएं
-
-
-
ठीक :=सच
-
लूप से बाहर आएं
-
-
-
-
-
एम खाली होने पर सही लौटें, अन्यथा गलत।
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int> nums, int k) {
map <int, int> m;
for(auto& it : nums){
m[it]++;
}
bool ok = true;
while(m.size() && ok){
ok = false;
for(auto& it : m){
if(!m.count(it.first - 1)){
bool flag = true;
for(int i = it.first; i <= it.first + k - 1;i++){
if(!m.count(i))
flag = false;
}
if(flag){
for(int i = it.first; i <= it.first + k - 1;i++){
m[i]--;
if(m[i] == 0)
m.erase(i);
}
ok = true;
break;
}
}
}
}
return m.empty();
}
};
main(){
vector<int> v = {4, 3, 2, 4, 5, 6};
Solution ob;
cout << ob.solve(v, 3);
}
इनपुट
{4, 3, 2, 4, 5, 6} आउटपुट
1