C++에서 배열을 연속적인 하위 시퀀스로 분할

<시간/>

오름차순으로 정렬된 배열 번호가 있다고 가정합니다. 각 부분 시퀀스가 연속적인 정수로 구성되고 길이가 최소 3이 되도록 1개 이상의 부분 시퀀스로 분할할 수 있는 경우에만 true를 반환해야 합니다. 따라서 입력이 [1,2,3,3,4, 4,5,5], 두 개의 연속 시퀀스가 있으므로 출력은 True가 됩니다. [1,2,3,4,5] 및 [3,4,5]입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m 맵을 만들고 nums의 빈도를 m에 저장하고 nums의 크기를 m에 저장
cnt :=n
0 ~ n – 1 범위의 i에 대해
- x :=숫자[i]
- m[x] 및 m[x + 1] 및 m[x + 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이면 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;
   }
};
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]