算法-分割数组为连续子序列

Bertha 。 2022-12-26 10:13 110阅读 0赞

# 算法-分割数组为连续子序列 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

# 2 贪心法 #

## 2.1 思路 ##

先统计每个数出现次数，然后从小到大开始组合：

1.  总是贪心地和比自己小1的数结尾的长度为1的子集组合，成为以当前数结尾的长度为2的子集
2.  剩下的数和比自己小1的数结尾的长度为2的子集组合，成为以当前数结尾的长度为3的子集
3.  最后剩下的数，和比自己小1的数结尾的长度至少为3的子集组合，成为以当前数结尾的长度为至少3+1的子集

最后，判断以最后一轮遍历的最大的数字结尾的长度为1和2的子集数是否都为0，如果为0则说明全部组合成了至少长度为3的子集，否则说明匹配组合失败，返回false即可。

这个解法最重点的思路就是，优先和上一个数长度为1的组合为长度为2的，也就是说总是和更短的子集组合，因为题目要求是必须组合成长度为3的。

## 2.2 代码 ##

class Solution { 
        public boolean isPossible(int[] nums) { 
            if(nums.length < 3){ 
                //总的数字个数小于3，肯定无法组成
                return false;
            }
            // 存储去重后数字，长度为最大值
            int[] distinctNums = new int[nums[nums.length - 1] - nums[0] + 1];
            if(distinctNums.length < 3){ 
                // 去重后数字个数小于3，肯定无法组成
                return false;
            }
            // 统计每个数字出现次数
            for(int num : nums){ 
                distinctNums[num - nums[0]]++;
            }
           
            // 记录比比当前遍历数小1的数结尾的，分长度为1、2、大于等于3的子集
            int one = 0, two = 0, three = 0;
    
            for(int i = 0; i < distinctNums.length; i++){ 
                // 1. 先和one匹配，组合为two
                distinctNums[i] -= one;
                // 2. 再和two匹配，组合为three
                distinctNums[i] -= two;
                if(distinctNums[i] < 0){ 
                    // 说明上一个数字结尾的数存在无法组合成长度至少为3的子集
                    return false;
                }
                // 记录下上一轮two子集数
                int tmpTwo = two;
                // 更新two
                two = one;
               
    
                // 3. 和three组合
                if(distinctNums[i] > three){ 
                    // 部分拿来和three组合, 
                    // 剩余的组成新的one
                    one = distinctNums[i] - three;
                    // 注意这里还需要加上本数前面已经和two组合形成的three
                    three += tmpTwo;
                } else{ 
                    // 此时distinctNums[i] <= three
                    // 全部拿来和three组合
                    // 注意这里还需要加上本数前面已经和two组合形成的three
                    three = distinctNums[i] + tmpTwo;
                    // 那就没有剩余元素组成one了
                    one = 0;
                }
            }
    
            // 最终必须不存在长度为1和2的子集才符合题意
            return one + two == 0;
        }
    }

## 2.3 时间复杂度 ##

O(N)

## 2.4 空间复杂度 ##

O(nums\[nums.length - 1\] - nums\[0\])

# 参考文档 #

*  [o(n)贪心，详细说明][o_n]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20221120/2df70dae813345f19fb88ee51fd42581.png
[o_n]: https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/solution/ontan-xin-xiang-xi-shuo-ming-by-i3old-6a-tlsw/