C++で配列を連続するサブシーケンスに分割する

昇順で並べ替えられた配列numがあるとします。各サブシーケンスが連続する整数で構成され、長さが少なくとも3になるように、1つ以上のサブシーケンスに分割できる場合にのみ、trueを返す必要があります。したがって、入力が[1,2,3,3,4、 4,5,5]の場合、2つの連続したシーケンスがあるため、出力はTrueになります。これらは[1,2,3,4,5]と[3,4,5]です。

これを解決するには、次の手順に従います-

• マップmを作成し、numsの頻度をmに格納し、numsのサイズをmに格納します
• cnt：=n
• 0からn–1の範囲のiの場合
  • x：=nums [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]

出力

1