सी ++ में लगातार बाद में विभाजित ऐरे

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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

• बेहतर समझने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -

उदाहरण

#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;
   }
};
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