Chia mảng thành các chuỗi con liên tiếp trong C ++

Giả sử chúng ta có một số mảng được sắp xếp theo thứ tự tăng dần. Chúng ta phải trả về true nếu và chỉ khi chúng ta có thể chia nó thành 1 hoặc nhiều dãy con sao cho mỗi dãy con bao gồm các số nguyên liên tiếp và có độ dài ít nhất là 3. Vì vậy, nếu đầu vào giống như [1,2,3,3,4, 4,5,5], thì đầu ra sẽ là True, vì chúng ta có hai chuỗi liên tiếp. Đây là [1,2,3,4,5] và [3,4,5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Lập bản đồ m và lưu trữ tần số của num vào m, lưu trữ kích thước của num vào m
• cnt:=n
• cho tôi trong phạm vi từ 0 đến n - 1
  • x:=nums [i]
  • nếu m [x] và m [x + 1] và m [x + 2]
  • giảm m [x], m [x + 1] và m [x + 2] đi 1, tăng x lên 3 và giảm số lượng đi 3
  • while m [x]> 0 và m [x]> m [x - 1]
    • giảm cnt đi 1, giảm m [x] đi 1 và tăng x lên 1
• trả về true nếu cnt là 0, ngược lại là false

• Hãy cho chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

1