659 Split Array into Consecutive Subsequences

Search…
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.The length of the input is in range of [1, 10000]
2. Implementation
(1) Heap
思路：建立一个map，每个序列当前结尾的number作为key, value是该number对应的minHeap,存储以该number结尾的序列的长度. 当一个number出现在两个或以上的序列的末端，我们尽量把number + 1加在最短的序列后面(所以用minHeap). 最后遍历整个map，当出现以key结尾的序列的长度小于3时，返回false
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
            minHeap.add(len + 1);
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)
502 IPO
668 Kth Smallest Number in Multiplication Table
Last modified 2yr ago
Copy link
Contents
659. Split Array into Consecutive Subsequences
1. Question
2. Implementation
3. Time & Space Complexity
659. Split Array into Consecutive Subsequences​

1. Question

2. Implementation

3. Time & Space Complexity

659. Split Array into Consecutive Subsequences
