659 Split Array into Consecutive Subsequences

# 1. Question

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
Input: [1,2,3,3,4,5]
2
3
Output: True
4
5
Explanation:
6
You can split them into two consecutive subsequences :
7
1, 2, 3
8
3, 4, 5
Copied!
Example 2:
1
Input: [1,2,3,3,4,4,5,5]
2
3
Output: True
4
5
Explanation:
6
You can split them into two consecutive subsequences :
7
1, 2, 3, 4, 5
8
3, 4, 5
Copied!
Example 3:
1
Input: [1,2,3,4,4,5]
2
3
Output: False
Copied!
Note:
1. 1.
The length of the input is in range of [1, 10000]

# 2. Implementation

(1) Heap

1
class Solution {
2
public boolean isPossible(int[] nums) {
3
if (nums == null || nums.length <= 2) {
4
return false;
5
}
6
7
Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
8
PriorityQueue<Integer> minHeap = null;
9
for (int num : nums) {
10
minHeap = map.getOrDefault(num - 1, new PriorityQueue<>());
11
int len = minHeap.size() == 0 ? 0 : minHeap.remove();
12
minHeap = map.getOrDefault(num, new PriorityQueue<>());
13
14
map.put(num, minHeap);
15
}
16
17
for (int key : map.keySet()) {
18
for (int len : map.get(key)) {
19
if (len < 3) {
20
return false;
21
}
22
}
23
}
24
return true;
25
}
26
}
Copied!
(2) Two HashMap
(1) 用一个map记录每个number出现的次数，用另一个map记录当前的number是否可以加到一个现有的subsequence里
(2) 对于每个数，它要不成为一个有连续3个数的subsequence的开头，要不可以加在一个现有的subsequence里，如果这两个条件都不满足，说明该数组不能split成题目要求的subsequence
1
class Solution {
2
public boolean isPossible(int[] nums) {
3
if (nums == null || nums.length <= 2) {
4
return false;
5
}
6
7
Map<Integer, Integer> freq = new HashMap<>();
8
Map<Integer, Integer> need = new HashMap<>();
9
10
for (int num : nums) {
11
freq.put(num, freq.getOrDefault(num, 0) + 1);
12
}
13
14
for (int num : nums) {
15
if (freq.get(num) == 0) continue;
16
17
// Current num can be appended to a subsequence
18
if (need.getOrDefault(num, 0) > 0) {
19
need.put(num, need.get(num) - 1);
20
need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
21
}
22
// Current num be the start of a new subsequence
23
else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {
24
freq.put(num + 1, freq.get(num + 1) - 1);
25
freq.put(num + 2, freq.get(num + 2) - 1);
26
need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
27
}
28
// We can not split the array into subsequences with at least 3 consecutive numbers due to current number
29
else {
30
return false;
31
}
32
freq.put(num, freq.get(num) - 1);
33
}
34
return true;
35
}
36
}
Copied!

# 3. Time & Space Complexity

HashMap + Heap: 时间复杂度O(nlogk + nk),k为以num为结尾的subsequence的个数 空间复杂度O(nk)
Two HashMap: 时间复杂度O(n), 空间复杂度O(n)