659.分割数组为连续子序列

题目来源:https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/

给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个长度为 3 的子序列,其中每个子序列都由连续整数组成。

如果可以完成上述分割,则返回 true ;否则,返回 false

示例 1:

**输入: **[1,2,3,3,4,5]

输出: True

解释:

你可以分割出这样两个连续子序列 :

1, 2, 3

3, 4, 5

示例 2:

**输入: **[1,2,3,3,4,4,5,5]

**输出: **True

解释:

你可以分割出这样两个连续子序列 :

1, 2, 3, 4, 5

3, 4, 5

示例 3:

输入: [1,2,3,4,4,5]

输出: False

提示:

1 <= nums.length <= 10000

解法

解法一:最优贪心算法

算法如下:

初始化:

n=nums.size(); // n为给定序列的长度

n1 = n2 = n3 = 0; // n1代表以prev为结尾的长度为1的序列个数,同理n2,n3为以prev为结尾的长度为>=3的序列个数

i = 0; // 计次变量

开始:

while(i<n){

​ prev = nums[i];

​ start = i;

​ while(i<n && nums[i] == prev)

​ i++;

​ cnt = i - start; //此处cnt得到的是重复出现的数字个数,cnt=1即未重复,i指向下一个元素。

​ if(start>0 && prev!=nums[start-1]+1){

​ // 当start不为第一个元素 且连续性被打破 即nums[start]无法拼接到以nums[start-1]为结尾的序列。

​ if(n1+n2>0) {

​ // 如果要满足能够划分长度不小于3的连续子序列,则此时n1与n2之和应为0,否则必然会出现长度小于3的连续子序列(以nums[start-1]结尾的序列)。

​ return false; // 提前结束判断

​ }else{

​ // 构造以nums[start]元素为结尾的连续子序列,其序列的个数为cnt,并且长度为1,因而对n1重新赋值,同时n2与n3置为0

​ n1 = cnt;

​ n2 = n3 = 0;

​ }

​ }else{

​ // 连续性未被打破,即nums[start]可以拼接到以nums[start-1]为结尾的序列之后。

​ if(n1+n2>cnt){

​ // 但这里需要判断cnt是否≥n1+n2,如若不是,则cnt个nums[start]只能拼接到n1+n2-cnt个以nums[start-1]结尾的连续子序列,n1+n2-cnt个子序列不满足长度不小于3的条件,不满足条件,返回false

​ return false;

​ }else{

​ // cnt>=n1+n2 更新n1、n2、n3的值

​ // 此时cnt个nums[start]将被添加到以nums[start-1]为结尾的子序列,此时n1、n2、n3分别表示以nums[start]结尾的长度为1、2、>=3的子序列个数。n3的来源有nums[start-1]结尾的子序列个数n2和cnt中添加到以nums[start+1]位结尾的长度≥3的子序列个数,即n3 = n2 + min(n3, cnt-n1-n2)。n2的来源只能是nums[start-1]结尾的子序列个数n1,即n2 = n1。n1的来源只能是cnt中补充了原先的n1、n2、n3之后还剩下来的,只能开辟新的子序列,即 cnt = cnt - n1 - n2 - min(n3, cnt-n1-n2)。

​ remnant = cnt - n1 - n2;

​ t = min(n3, remnant);

​ n3 = n2 + t;

​ n2 = n1;

​ n1 = remnant - t;

​ // 注意赋值顺序

​ }

​ }

}

return (n1==0 && n2==0); // 遍历完序列之后,判断存在n1、n2为0的序列,若无,则返回true

实现代码如下(C++):

class Solution {
// better greedy algorithm
public:
    bool isPossible(vector<int>& nums) {
        int n=nums.size();
        int n1=0,n2=0,n3=0;
        int i;
        while(i<n){
            int prev = nums[i];
            int start = i;
            while(i<n && nums[i] == prev) i++;
            int cnt = i - start;  // count of nums[start]
            if(start > 0 && prev!= nums[start-1]+1){
                if(n1+n2>0) return false;
                else{
                    n1 = cnt;
                    n2 = n3 = 0;
                }
            }else{
                if(n1+n2>cnt) return false; // cnt cannot supply for both n1 and n2
                else{
                    int remnant = cnt - n1 - n2;
                    int t = min(n3, remnant);
                    n3 = n2 + t;  // n3 consists of previous n2 and t (which new prev link with n3 successfully)
                    n2 = n1;  // n2 consists of previous n1
                    n1 = remnant - t;  // n1 consists of prev which cannot link to a new sequence
                }
            }
        }
        return (n1==0 && n2==0);
    }
};

复杂度分析:

时间复杂度:O(n)

空间复杂度:O(1)


解法二:哈希表 + 最小堆

此解法参考了官方题解,哈希表的键为子序列的最后一个数字,值为最小堆,用于存储所有的子序列长度,最小堆满足堆顶的元素是最小的,因此堆顶的元素即为最小的子序列长度。

算法如下:

遍历数组,当遍历到元素 x 时,可以得到一个以 x 结尾的子序列。

(1)如果哈希表中存在以 x-1 结尾的子序列,则取出以 x-1 结尾的最小的子序列长度,将子序列长度加 1之后作为以 x 结尾的子序列长度。此时,以 x-1结尾的子序列减少了一个,以 x 结尾的子序列增加了一个。

(2)如果哈希表中不存在以 x-1 结尾的子序列,则新建一个长度为 1 的以 x结尾的子序列。

由于数组是有序的,因此当遍历到元素x 时,数组中所有小于 x的元素都已经被遍历过,不会出现当前元素比之前的元素小的情况。

遍历结束之后,检查哈希表中存储的每个子序列的长度是否都不小于 3,即可判断是否可以完成分割。由于哈希表中的每条记录的值都是最小堆,堆顶元素为最小的子序列长度(以当前的键为最后一个数字的子序列),因此只要遍历每个最小堆的堆顶元素,即可判断每个子序列的长度是否都不小于 3

具体实现如下(C++):

class Solution1 {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> hashmap;
        int length = nums.size();
        for(int item: nums){
            if(hashmap.count(item) == 0){
                hashmap[item] = priority_queue<int, vector<int>, greater<int>>();
            }
            if(hashmap.count(item-1)!=0){
                int prev = hashmap[item-1].top();
                hashmap[item-1].pop();
                hashmap[item].push(prev+1);
                if(hashmap[item-1].empty()){
                    hashmap.erase(item-1);
                }
            }else{
                hashmap[item].push(1);
            }
        }
        for(int item: nums){
            if(!hashmap[item].empty() && hashmap[item].top() < 3)
                return false;
        }
        return true;
    }
};

复杂度分析:

时间复杂度:O(nlogn) 维护最小堆的时间复杂度为O(logn),外层循环遍历整个序列,时间复杂度为O(n),因而整体时间复杂度为O(nlogn)

空间复杂度:O(n) 需用到哈希表