659. split array into consecutive subsequences-leetcode

PAT乙级的题太简单，甲级的题又都差不多做过了，所以今天继续来做做LeetCode的题好了。

题目：Split Array into Consecutive Subsequences

难度：Medium

要求：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.

用例：

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5

解读：
刚拿到这道题的时候，确实没想到应该怎么解，看来算法方面的题做得还是太少了，之后知道了这题需要用到贪心算法，具体难度在于要搞清楚在一个数字有多个的时候，应该怎么分配它，是就以它结尾，还是说和后面的数字连在一起，这就需要一个表，可以是哈希表，来记录以每个数字结尾的序列有多少，这样就能随时判断，是否将这一序列与后面的序列接在一起。

具体思路：
这里借用大多数人的思路，需要维护两个哈希表 heap 和 last. heap 表记录给出的数组中每个数字出现的次数，而 last 表则记录以某个数字结尾的长度不小于2的连续序列的个数。

首先第一次遍历数组，用 heap 数组记录每个数字出现的次数，当然，有的人将这一步骤与第二步骤写到了一起，后面会说到。

然后是第二次遍历数组，对遍历到的每一个数字 num，如果 last[num - 1] > 0 ，说明存在以 num - 1 为结尾的连续序列，则把数字 num 添加到该连续序列中：代码为 last[num - 1]—; last[num]++。其实就算 num 是另一连续序列的开始，也不要紧，因为如果是的话，把这两个序列和在一起，分开，对结果并没有什么影响：比如 [1, 2, 3] 和 [4, 5, 6] 两个连续序列是可以合并成 [1, 2, 3, 4, 5, 6] 这个大的连续序列的；当然，如果 last[num - 1] == 0 ，此时我们就需要以 num 为开始数字建立一个新的连续序列。这时就要检查 num + 1 和 num + 2 这两个数字是否存在，如果不存在，则直接 return false ，否则，新建以 num + 2 数字为结尾的连续序列。

如果上述过程能进行到最后，说明所有连续序列都能够找出来，则直接 return true。

具体代码如下：

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
26
27
28

class  {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> heap, last;

        for (int &num : nums) { heap[num]++; }
        for (int &num : nums) {
            
            // 一个包含当前数字 num 的连续序列，直接跳过扫描下一个数字
            if (heap[num] <= 0) { continue; }
            heap[num]--;

            if (last[num - 1] > 0) {
                last[num - 1]--;
                last[num]++;
            } else if (heap[num + 1] && heap[num + 2]) {
                // 新建连续序列，要把包含进新序列的数字的出现次数也减 1
                heap[num + 1]--;
                heap[num + 2]--;
                last[num + 2]++;
            } else {
                return false;
            }
        }

        return true;
    }
};

当然也有 Python 版本的解法，它将两个遍历过程弄到一个里面去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class (object):
    def isPossible(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        saved = collections.defaultdict(list)
        for num in nums:
            last = saved[num - 1]
            _len = 0 if (not last) else heapq.heappop(last)
            current = saved[num]
            heapq.heappush(current, _len + 1)
        for values in saved.values():
            for v in values:
                if v < 3:
                    return False
        return True