配列をC++のK個の連続した数値のセットに分割します

整数numsと正の整数kの配列があるとすると、この配列をk個の連続した数のセットに分割できるかどうかを調べる必要があります。したがって、可能であればTrueを返す必要があり、そうでない場合はFalseを返す必要があります。したがって、入力が[1,2,3,3,4,4,5,6]のようで、k =4の場合、出力はtrueになります。これは、[1,2,3,4]と[3,4,5,6]

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

• 1つのマップmを作成し、n：=nums配列のサイズを設定します
• numsの各要素eについて
  • m[e]を1増やします
• cnt：=0
• 並べ替えnums配列
• 0からnの範囲のiの場合
  • x：=nums [i]
  • m [x – 1]=0かつm[x]>0
    の場合
    • l：=k
    • while k> 0
      • m [x]> 0の場合、m [k]の値を1減らし、それ以外の場合はfalseを返します
      • xとcntを1増やし、kを1減らします
    • k：=l
• cnt =nの場合はtrueを返し、それ以外の場合はfalseを返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool isPossibleDivide(vector<int>& nums, int k) {
      map <int, int> m;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         m[nums[i]]++;
      }
      int cnt = 0;
      sort(nums.begin(), nums.end());
      for(int i = 0; i < n; i++){
         int x = nums[i];
         if(m[x - 1] == 0 && m[x] > 0){
            int l = k;
            while(k>0){
               if(m[x] > 0){
                  m[x]--;
            } else return false;
               x++;
               k--;
               cnt++;
            }
            k = l;
         }
      }
     return cnt == n;
   }
};
main(){
   vector<int> v = {1,2,3,3,4,4,5,6};
   Solution ob;
   cout << (ob.isPossibleDivide(v, 4));
}

入力

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

出力

1