在 C++ 中将数组分成 K 个连续数字的集合
c++server side programmingprogramming更新于 2024/11/8 20:36:00
假设我们有一个整数数组 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
- 对 nums 数组进行排序
- 对于 i 在 0 到 n 范围内
- x := nums[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
