LEETCODE 1296. Divide Array in Sets of K Consecutive Numbers 解题思路分析

题目大意:

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

给你一个整数数组 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

LEETCODE 1296. Divide Array in Sets of K Consecutive Numbers 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 846. Hand of Straights 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。