関小君刷题记

题目大意：

划分数组为连续数字的集合

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
如果可以，请返回 True；否则，返回 False。

示例 1：

输入：nums = [1,2,3,3,4,4,5,6], k = 4
输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

示例 2：

输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。

示例 3：

输入：nums = [3,3,2,2,1,1], k = 3
输出：true

示例 4：

输入：nums = [1,2,3,4], k = 3
输出：false
解释：数组不能分成几个大小为 3 的子数组。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= nums.length

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1296

解题思路分析：

1. 首先判断一下数组的长度是否能被k整除，如果不能肯定无法分组，直接返回false。
2. 升序排序数组。
3. 从数组首位开始找到k个连续数字（长度为k的子序列）。如果找不到直接返回false。将使用过的数字赋值为0，避免重复使用。
4. 再从数组开头位置开始找到值不为0的k个连续数字，重复此步骤，直到数组所有值都被用完，返回true。如果循环过程中找不到相应的数字时，直接返回false。

如果理解了本题思路，强烈建议利用下面一题来作为联系，因为这两题的描述几乎是一模一样的，LEETCODE 846. Hand of Straights 解题思路分析

实现代码：

public boolean isPossibleDivide(int[] nums, int k) {
    // 数组的长度不能被k整除时，返回false
    if(nums.length%k!=0) return false;
    // 排序数组
    Arrays.sort(nums);
    // 从头循环每个数字
    for(int i=0;i<=nums.length-k;i++){
        // 如果该数字不为0（没被使用过）
        if(nums[i]>0){
            // 看是否能够找到k个连续数字，找不到直接返回false
            if(!help(nums, k-1, i,nums[i])) return false;
        }
    }
    return true;
}
// 找到k个连续数字
// nums为原始数组
// k是需要找到连续数字的个数
// preIndex为上一个数字的位置
// preNum是上一个数字的值
// 返回值为是否能找到k个连续数字
boolean help(int[] nums, int k, int preIndex, int preNum){
    if(k==0) return true; // k为0，直接返回true
    int current = preNum+1; // 当前数字应为前数字加一
    // 从上一个数字之后的一位向后循环，找到一个等于当前数字的数
    for(int i=preIndex+1;i<nums.length;i++){
        // 当前位的数
        int n=nums[i];
        // 如果当前位置的数大于current，返回false。
        // 因为数组已排序过，如果当前数已经大于current，后面的数一定也都大于current
        if(n>current) return false;
        // 如果n为0，表示已经被使用过，跳过。
        if(n==0) continue;
        // 如果n等于current，表示找到了连续数字
        if(n==current){
            // 当前位设置为0
            nums[i]=0;
            // 递归寻找下一位连续数字
            return help(nums,k-1,i,current);
        }
    }
    return false;
}

本题解法执行时间为267ms。

Runtime: 267 ms, faster than 12.59% of Java online submissions for Divide Array in Sets of K Consecutive Numbers.

Memory Usage: 52.8 MB, less than 100.00% of Java online submissions for Divide Array in Sets of K Consecutive Numbers.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1296-divide-array-in-sets-of-k-consecutive-numbers-解题思路分析/