659. Split Array into Consecutive Subsequences
problem desctiption
Given an array nums
sorted in ascending order, return true
if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.
Example 1:
Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5
Example 2:
Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5
Example 3:
Input: [1,2,3,4,4,5]
Output: False
Constraints:
1 <= nums.length <= 10000
algorithm description
第一次想这题,没看清是连续的数字。导致分析了很久也没结果。知道是连续的数字之后,就很好办了。可以直接用hashmap保存数字出现的次数,以及保存3个以上链表的末尾节点,每次访问到数字,首先查看链表后面末尾节点是否有值,有的话直接加一。如果没有,就将这个数字后面两个数字和这个组合起来,然后加入到将这个链表末尾节点加入hashmap,如果不能进行上面两个操作,说明这里有问题
code
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int,int> cut,tail;
for(auto num:nums)
cut[num]++;
for(auto n:nums){
if(cut[n]<=0)
continue;
cut[n]--;
if(tail[n-1]){
tail[n-1]--;
tail[n]++;
}else if(cut[n+1]&&cut[n+2]){
cut[n+1]--;cut[n+2]--;
tail[n+2]++;
}else
return false;
}
return true;
}
};
algorithm analysis
two-pass解决问题,时间复杂度O(n).hashmap插入操作时间也是O(1)。
Last updated