659. Split Array into Consecutive Subsequences

发表于 | 分类于 | |

659. Split Array into Consecutive Subsequences

题目描述

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Example 1:

1
2
3
4
5
6
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:

1
2
3
4
5
6
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:

1
2
Input: [1,2,3,4,4,5]
Output: False

Note:
The length of the input is in range of [1, 10000]

题目大意

将一有序数组，拆分成多个递增子序列。（每个子序列至少三个）

解题思路

一个字典 dict 记录剩余 num 的个数
另一个字典 tail 则记录当前的 num 是否可以被拼接到之前的子序列。
如果不可以则重新启动一个新的序列，但是新的序列需要满足至少有三个 num 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    func isPossible(_ nums: [Int]) -> Bool {
        var dict = [Int: Int]()
        var tail = [Int:Int]()
        for num in nums {
            dict[num] = (dict[num] ?? 0) + 1
        }
        for num in nums {
            if let c = dict[num], c == 0 {
                continue
            } else if let c = tail[num], c > 0 {
                tail[num] = c - 1
                tail[num + 1] = (tail[num + 1] ?? 0) + 1
            } else if let c1 = dict[num + 1], c1 > 0, let c2 = dict[num + 2], c2 > 0 {
                dict[num + 1] = c1 - 1
                dict[num + 2] = c2 - 1
                tail[num + 3] = (tail[num + 3] ?? 0) + 1
            } else {
                return false
            }
            dict[num]! -= 1
        }
        return true
    }
}
0%