26分割数组为连续子序列(659)

作者: Turbo时间限制: 1S章节: 贪心

晚于: 2020-07-22 12:00:00后提交分数乘系数50%

截止日期: 2020-07-29 12:00:00

问题描述 :

给你一个按升序排序的整数数组 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, 10000]

输入说明 :

首先输入num的长度n，然后输入n个整数

输出说明 :

输出“true”或“false”，不包括引号。

输入范例 :

8 1 2 3 3 4 4 5 5

输出范例 :

true

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    bool isPossible(vector<int>& nums) 
    {
        unordered_map<int,int> sum,i_tail;//sum存储各个数字出现的次数，i_tail存储以i结尾并符合条件的数组数目
        for(auto x:nums) //统计每个元素出现的次数 
            sum[x]+=1;
        for(auto x:nums)
        {
            if(sum[x]!=0&&i_tail[x-1]) //如果 sum[x]!=0&&i_tail[x-1]都存在，可以将x接在x-1后面 
            {
                sum[x]--;
                i_tail[x-1]--;
                i_tail[x]++;
            }
            else if(sum[x]==0)//元素使用完，继续 
                continue;
            else 
            {
                if(sum[x]&&sum[x+1]&&sum[x+2])//如果无法接入，重新建立三个元素组 
                {
                    sum[x]--;
                    sum[x+1]--;
                    sum[x+2]--;
                    i_tail[x+2]++;
                }
                else//都不满足，则返回false 
                    return false;
                
            }
                
        }
    return true;    
    }
};
int main()
{
    int n,data;
    cin>>n;
    vector<int> nums;
    for(int i=0;i<n;i++) 
    {
        cin>>data;
        nums.push_back(data);
    }
    if(Solution().isPossible(nums))
        cout<<"true";
    else
        cout<<"false";
    return 0;
}
//https://blog.csdn.net/qq_41855420/article/details/89378748
//https://www.cnblogs.com/lancelee98/p/13286408.html