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]

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

• 하나의 맵을 m으로 만들고 n :=nums 배열의 크기로 설정
• nums
  의 각 요소 e에 대해
  • m[e] 1 증가
• cnt :=0
• 숫자 배열 정렬
• 0~n
  범위의 i에 대해
  • x :=숫자[i]
  • m[x – 1] =0이고 m[x]> 0인 경우
    • l :=k
    • 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