[LeetCode] 1296. Divide Array in Sets of K Consecutive Numbers #1296

grandyang · 2019-05-30T16:34:19Z

Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.

Return true if it is possible. Otherwise, return false.

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 = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= k <= nums.length <= 105
1 <= nums[i] <= 109

Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/

这道题给了一个数组 nums 和一个正整数k，问可不可以将原数组分为k个子数组，使得每个子数组中的数字是连续的，参考题目中给的例子不难理解题意。这道题就是之前那道 Hand of Straights，一模一样，换了个场景而已。目前 LeetCode 已有两千多道题目，会出现完全相同的题目也是可以理解的，毕竟出题人也不一定刷完了所有的题目。就算是刷同样的题目，若间隔很久的话，有时也会有新的想法冒出来，就算没有的话，权当复习也不错。博主最先的想法是用贪婪算法 Greedy Algorithm，就像打牌找顺子一样，首先要理牌，直接排序是一种方法，但不是最好的，因为可能有很多重复数字，可以建立数字和其出现次数之间的映射，同时这里需要用 TreeMap，从而得以得到有序的排列。

既然要分成k个子数组，若原数组长度为n，则n必须能被k整除，每个子数组的长度就是 n/k，那么可以遍历 n/k 次，来验证每个连续数字的子数组是否存在。先将 numCnt 中的第一个映射对儿的数字取出来，存到 start 中，然后验证是否有k个连续的数字存在，将对应的映射值自减1，若小于0了，说明数字不够了，不能组成连续的数字，返回 false；若等于0了，则将映射对儿移除，因为每次开头时都要取最小的数字。循环退出后返回 true 即可，参见代码如下：

解法一：

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        int n = nums.size();
        if (n % k != 0) return false;
        map<int, int> numCnt;
        for (int num : nums) ++numCnt[num];
        for (int i = 0; i < n / k; ++i) {
            int start = numCnt.begin()->first;
            for (int j = start; j < start + k; ++j) {
                if (--numCnt[j] < 0) return false;
                if (numCnt[j] == 0) numCnt.erase(j);
            }
        }
        return true;
    }
};

再来看一种大同小异的方法，这里的思路是从最小的数字开始，若其有 freq 个，那么连续的k个数字一定至少也得有 freq 个才能保证分组成功，否则无法匹配。这样的话，就可以将连续的k个数字的映射值都减去 freq，若其中有任何映射值小于0了，直接返回 false，否则就继续从新的最小数字开始相同的操作（注意需要跳过映射值为0的数字），参见代码如下：

解法二：

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        int n = nums.size();
        if (n % k != 0) return false;
        map<int, int> numCnt;
        for (int num : nums) ++numCnt[num];
        for (auto &a : numCnt) {
            if (a.second <= 0) continue;
            int start = a.first, freq = a.second;
            for (int i = 0; i < k; ++i) {
                numCnt[start + i] -= freq;
                if (numCnt[start + 1] < 0) return false;
            }
        }
        return true;
    }
};

Github 同步地址:

#1296

类似题目：

Hand of Straights

Split Array into Consecutive Subsequences

All Divisions With the Highest Score of a Binary Array

参考资料：

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/discuss/457569/C%2B%2B-Greedy

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/discuss/470238/JavaC%2B%2BPython-Exactly-Same-as-846.-Hand-of-Straights

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）