首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >分割数组为连续子序列 (难度:中等) - Day20201204

分割数组为连续子序列 (难度:中等) - Day20201204

作者头像
前端小书童
发布2020-12-17 11:29:06
4640
发布2020-12-17 11:29:06
举报
文章被收录于专栏:前端小书童前端小书童

20201204

题目:

给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个子序列,其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割,则返回 true ;否则,返回 false 。

示例:

  1. 示例 1:
输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5
  1. 示例 2:
输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5
  1. 示例 3:
输入: [1,2,3,4,4,5]
输出: False

提示:

  • 输入的数组长度范围为 [1, 10000]

抛砖引玉

思路:

贪心

抛砖引玉

从前到后遍历 nums,模拟分割子序列,对应遇到的任意元素,其可以作为新子序列的起点也可以附加到前一个子序列。

以为题目要求子序列最少要三个元素,那么保证子序列满足要求,优先将遇到的子序列附加到前一个子序列:

  1. 遍历 nums 记录每个元素出现的次数
  2. 逐个取 nums 元素 item(map 统计数量减少):
    • item 出现次数和其之后的两个元素数量均大于 0,则他们可以作为一个新子序列存在,新子序列的结尾为 item+3
    • 如果 item 是一个子序列的结尾,那么优先将其附加到上一个子序列,将其后一个元素看做子序列的结尾 item+1
    • 如果 nums 所有元素均可以按照上面逻辑分割成子序列,则返回 true,否则返回 false

注意: 在标记元素作为子序列结尾时,其可以存在也可以不存在,因为前面的序列已经满足题目要求

var isPossible = function(nums) {
    const len = nums.length
    if (len < 3) return false
    let countMap = new Map(),
        map = new Map()
    // 统计每个数字出现的次数
    for (let i = 0; i < len; i++) {
        const num = countMap.get(nums[i]) || 0
        countMap.set(nums[i], num + 1)
    }
    // 模拟分割 优先附加到先前构造的连续序列中
    for (let i = 0; i < len; i++) {
        const item = nums[i],
            // 一组三个连续数组
            num = countMap.get(item) || 0,
            next1 = countMap.get(item + 1) || 0,
            next2 = countMap.get(item + 2) || 0,
            // 动态记录元素作为子序列结束的次数
            end = map.get(item) || 0,
            endNext1 = map.get(item + 1) || 0,
            endNext2 = map.get(item + 3) || 0
        // 如果数字出现次数归零,则进行向后查找
        if (num === 0) continue
        // 遇到可以作为子序列结束的元素,将其附加到前子序列,其下一个元素代替其作为子序列的结尾
        if (end > 0) {
            map.set(item, end - 1)
            map.set(item + 1, endNext1 + 1)
        } else if (next1 > 0 && next2 > 0) {
            // 连续三个数后标记一个可能的子序列结尾
            countMap.set(item + 1, next1 - 1)
            countMap.set(item + 2, next2 - 1)
            map.set(item + 3, endNext2 + 1)
        } else {
            // 如果数组中遇到既不是子序列结尾,右不能组成新子序列的元素,则直接返回false
            return false
        }
        countMap.set(item, num - 1)
    }
    return true
}

博客: 前端小书童

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号:前端小书童

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-12-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 前端小书童 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目:
    • 示例:
    • 抛砖引玉
      • 贪心
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档