1296. Divide Array in Sets of K Consecutive Numbers

问题：

给定数组，和整数k

是否能将数组刚好平均分配为，每k个一组连续递增子数组。

Example 1:
Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:
Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:
Input: nums = [3,3,2,2,1,1], k = 3
Output: true

Example 4:
Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.
 
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

解法：

解法一：

首先将原数组元素计数，到map【nummap】中

遍历 nummap，每k个为一组，

nummap[0]，为小组第一个元素为准，以后的k-1个元素出现次数都-第一个元素出现的次数n（k-1个元素剩下的次数覆盖原值），

证明以第一个元素为首，首先能分成n个小组。

若以后的k-1个元素出现次数 < 第一个元素出现的次数n，那直接返回false。

然后继续遍历第二个元素nummap[1]，为小组第一个元素。重复上述操作。

最终遍历完nummap所有元素，都没有返回false。那么证明分配完毕。

返回true。

代码参考：

 1 class Solution {
 2 public:
 3     bool isPossibleDivide(vector<int>& nums, int k) {
 4         if(nums.size()%k) return false;
 5         map<int,int> nummap;
 6         for(int n:nums){
 7             nummap[n]++;
 8         }
 9         for(auto nm:nummap){
10             if(nm.second>0){
11                 for(int j=nm.first; j<nm.first+k; j++){
12                     if(nummap[j]<nm.second) return false;
13                     nummap[j]-=nm.second;
14                 }
15             }
16         }
17         return true;
18     }
19 };

解法二：

使用queue记录，当前开启的k个元素的小组个数。

这个queue最多保存时长为k，即size为k。

因为，假如当前遍历完第x个元素（记录完当前开启的小组数queue.push），在第x-k个元素时，所开启的小组，

到现在为止，已经连续保存了k个数值了，是时候结束生命周期。因此此时，需要关闭遍历x-k个元素时，所开启的小组。

opened记录当前开启的总小组个数，也即是当前元素的出现个数cout。

lastchecked记录当前元素val。

首先同解法一，

将原数组元素计数，到map【nummap】中

遍历 nummap，第一个元素val出现次数 cout

那么当前开启的小组数为cout

判断：如果当前元素val和上一个元素lastchecked不连续：opened>0 && val>lastchecked+1

或者，当前元素出现次数 < 当前开启的小组总数opened，那么直接返回 false。

若满足题意，未返回false。

那么将新追加开启的小组个数 cout-opened 存入queue中。queue.push

更新当前总开启组数opened和上一次检查元素对象lastchecked

加完当前元素后，判断queue的size是否到达k，

到达的时候，弹出最早开启中的小组。视为关闭。更新当前开启的小组总数opened-=queue.front。

当遍历完所有元素后，opened的个数应为0，才说明刚好分配完毕。

若不为0，那么返回false。

代码参考：

 1 class Solution {
 2 public:
 3     bool isPossibleDivide(vector<int>& nums, int k) {
 4         if(nums.size()%k) return false;
 5         map<int,int> nummap;
 6         for(int n:nums){
 7             nummap[n]++;
 8         }
 9         queue<int> start;
10         int opened=0, lastchecked=-1;
11         for(auto nm:nummap){
12             int val=nm.first;
13             int cout=nm.second;
14             if(opened>0 && val>lastchecked+1 || opened>cout) return false;
15             start.push(cout-opened);
16             opened=cout;
17             lastchecked=val;
18             if(start.size()==k){
19                 opened-=start.front();
20                 start.pop();
21             }
22         }
23         return opened==0;
24     }
25 };

1296. Divide Array in Sets of K Consecutive Numbers

相关推荐