Chia mảng trong tập hợp K số liên tiếp trong C ++

Giả sử chúng ta có một mảng các số nguyên num và một số nguyên dương k, chúng ta phải tìm xem có thể chia mảng này thành các bộ k số liên tiếp hay không. Vì vậy, chúng ta phải trả về True nếu nó có thể, nếu không thì trả về False. Vì vậy, nếu đầu vào là [1,2,3,3,4,4,5,6] và k =4, thì đầu ra sẽ là true. Điều này là do, chúng ta có thể chia mảng sao cho [1,2,3,4] và [3,4,5,6]

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

• Tạo một bản đồ m, đặt n:=kích thước của mảng nums
• cho mỗi phần tử e trong nums
  • tăng m [e] thêm 1
• cnt:=0
• sắp xếp mảng nums
• cho tôi trong phạm vi từ 0 đến n
  • x:=nums [i]
  • nếu m [x - 1] =0 và m [x]> 0
    • l:=k
    • while k> 0
      • nếu m [x]> 0, thì hãy giảm giá trị của m [k] đi 1, nếu không trả về false
      • tăng x và cnt lên 1 và giảm k đi 1
    • k:=l
• trả về true khi cnt =n, ngược lại là false

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

Ví dụ

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

Đầu vào

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

Đầu ra

1