经典算法思想题目-分割数组为连续子序列
给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个子序列,其中每个子序列都由连续整数组成且长度至少为 3 。
如果可以完成上述分割,则返回 true ;否则,返回 false 。
先统计每个数出现次数,然后从小到大开始组合:
总是贪心地和比自己小1的数结尾的长度为1的子集组合,成为以当前数结尾的长度为2的子集 剩下的数和比自己小1的数结尾的长度为2的子集组合,成为以当前数结尾的长度为3的子集 最后剩下的数,和比自己小1的数结尾的长度至少为3的子集组合,成为以当前数结尾的长度为至少3+1的子集 最后,判断以最后一轮遍历的最大的数字结尾的长度为1和2的子集数是否都为0,如果为0则说明全部组合成了至少长度为3的子集,否则说明匹配组合失败,返回false即可。
这个解法最重点的思路就是,优先和上一个数长度为1的组合为长度为2的,也就是说总是和更短的子集组合,因为题目要求是必须组合成长度为3的。
示例 1:
输入: [1,2,3,3,4,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3 3, 4, 5
示例 2:
输入: [1,2,3,3,4,4,5,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3, 4, 5 3, 4, 5
示例 3:
输入: [1,2,3,4,4,5] 输出: False
提示:
-
输入的数组长度范围为 [1, 10000]
解法:贪心算法
从头开始,我们每次仅仅寻找满足条件的序列(连续子序列长度为3),剔除之后,依次往后遍历:
-
判断当前元素是否能够拼接到前一个满足条件的连续子序列上,可以的话,则拼接 如果不可以,则判断以当前元素开始能否构成连续子序列(长度为3),可以的话,则剔除连续子序列 否则,返回 false
const isPossible = function(nums) { let max = nums[nums.length - 1] // arr:存储原数组中数字每个数字出现的次数 // tail:存储以数字num结尾的且符合题意的连续子序列个数 let arr = new Array(max + 2).fill(0), tail = new Array(max + 2).fill(0) for(let num of nums) { arr[num] ++ } for(let num of nums) { if(arr[num] === 0) continue else if(tail[num-1] > 0){ tail[num-1]-- tail[num]++ }else if(arr[num+1] > 0 && arr[num+2] > 0){ arr[num+1]-- arr[num+2]-- tail[num+2]++ } else { return false } arr[num]-- } return true }
复杂度分析:
-
时间复杂度:O(n) 空间复杂度:O(n)