腾讯&leetcode659：分割数组为连续子序列 #117

Activity

1. sisterAn

   added

   腾讯

   LeetCode

   on Oct 14, 2020
2. sisterAn commented on Oct 16, 2020

   

   sisterAn

   on Oct 16, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解法：贪心算法

   从头开始，我们每次仅仅寻找满足条件的序列（连续子序列长度为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)

   leetcode