数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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]。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个map 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
更新于：2020年5月2日
229 次浏览
广告