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:

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

Example 2:

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

Example 3:

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

Note:

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

给一个升序排列的整数数(可能含有重复元素)，把这个数组拆分成几个至少含有3个整数的子序列，求是否可以拆分成功？（也就是能够全部拆分组成顺子）

解法：贪婪算法Greedy

Java:

public boolean isPossible(int[] nums) {    Map
     
       freq = new HashMap<>(), appendfreq = new HashMap<>();    for (int i : nums) freq.put(i, freq.getOrDefault(i,0) + 1);    for (int i : nums) {        if (freq.get(i) == 0) continue;        else if (appendfreq.getOrDefault(i,0) > 0) {            appendfreq.put(i, appendfreq.get(i) - 1);            appendfreq.put(i+1, appendfreq.getOrDefault(i+1,0) + 1);        }           else if (freq.getOrDefault(i+1,0) > 0 && freq.getOrDefault(i+2,0) > 0) {            freq.put(i+1, freq.get(i+1) - 1);            freq.put(i+2, freq.get(i+2) - 1);            appendfreq.put(i+3, appendfreq.getOrDefault(i+3,0) + 1);        }        else return false;        freq.put(i, freq.get(i) - 1);    }    return true;}
     

Python:

# Time:  O(n)# Space: O(1)class Solution(object):    def isPossible(self, nums):        """        :type nums: List[int]        :rtype: bool        """        pre, cur = float("-inf"), 0        cnt1, cnt2, cnt3 = 0, 0, 0        i = 0        while i < len(nums):            cnt = 0            cur = nums[i]            while i < len(nums) and cur == nums[i]:                cnt += 1                i += 1            if cur != pre + 1:                if cnt1 != 0 or cnt2 != 0:                    return False                cnt1, cnt2, cnt3 = cnt, 0, 0            else:                if cnt < cnt1 + cnt2:                    return False                cnt1, cnt2, cnt3 = max(0, cnt - (cnt1 + cnt2 + cnt3)), \                                   cnt1, \                                   cnt2 + min(cnt3, cnt - (cnt1 + cnt2))            pre = cur        return cnt1 == 0 and cnt2 == 0

Python:

def isPossible(self, nums):        left = collections.Counter(nums)        end = collections.Counter()        for i in nums:            if not left[i]: continue            left[i] -= 1            if end[i - 1] > 0:                end[i - 1] -= 1                end[i] += 1            elif left[i + 1] and left[i + 2]:                left[i + 1] -= 1                left[i + 2] -= 1                end[i + 2] += 1            else:                return False        return True　　

C++:

class Solution {public:	bool isPossible(vector
     
      & nums)	{		unordered_map
      

, std::greater

>> backs; // Keep track of the number of sequences with size < 3 int need_more = 0; for (int num : nums) { if (! backs[num - 1].empty()) { // There exists a sequence that ends in num-1 // Append 'num' to this sequence // Remove the existing sequence // Add a new sequence ending in 'num' with size incremented by 1 int count = backs[num - 1].top(); backs[num - 1].pop(); backs[num].push(++count); if (count == 3) need_more--; } else { // There is no sequence that ends in num-1 // Create a new sequence with size 1 that ends with 'num' backs[num].push(1); need_more++; } } return need_more == 0; }};