C++ में सरणी को लगातार उपअनुक्रमों में विभाजित करना

मान लीजिए हमारे पास एक सरणी nums है जो आरोही क्रम में क्रमबद्ध है। हमें true लौटाना है यदि और केवल यदि हम इसे 1 या अधिक उपअनुक्रमों में विभाजित कर सकते हैं जैसे कि प्रत्येक उपअनुक्रम में लगातार पूर्णांक हों और जिसकी लंबाई कम से कम 3 हो। इसलिए यदि इनपुट [1,2,3,3,4,4,5,5] है, तो आउटपुट True होगा, क्योंकि हमारे पास दो लगातार अनुक्रम हैं: [1,2,3,4,5] और [3,4,5]।

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

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• एक मैप m बनाएं और nums की आवृत्ति को m में संग्रहीत करें, nums का आकार n में संग्रहीत करें
• cnt := n
• i = 0 से n-1 तक:
  • x := nums[i]
  • यदि m[x] और m[x+1] और m[x+2]:
    • m[x], m[x+1], m[x+2] को 1 से घटाएं, x को 3 से बढ़ाएं और cnt को 3 से घटाएं
    • while m[x] > 0 और m[x] > m[x-1]:
      • cnt को 1 से घटाएं, m[x] को 1 से घटाएं और x को 1 से बढ़ाएं
• यदि cnt == 0 तो true लौटाएं, अन्यथा false

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    bool isPossible(vector<int>& nums) { 
        unordered_map<int, int> m; 
        int n = nums.size(); 
        for(int i = 0; i < n; i++){ 
            m[nums[i]]++; 
        } 
        int cnt = n; 
        for(int i = 0; i < n; i++){ 
            int x = nums[i]; 
            if(m[x] && m[x + 1] && m[x + 2]){ 
                m[x]--; 
                m[x + 1]--; 
                m[x + 2]--; 
                x += 3; 
                cnt -= 3; 
                while(m[x] > 0 && m[x] > m[x - 1]){ 
                    cnt--; 
                    m[x]--; 
                    x++; 
                } 
            } 
        } 
        return cnt == 0; 
    } 
}; 

int main(){ 
    vector<int> v = {1,2,3,3,4,4,5,5}; 
    Solution ob; 
    cout << (ob.isPossible(v)); 
}

इनपुट

[1,2,3,3,4,4,5,5]

आउटपुट

1