一天一大 leet

题目(难度:困难):

给定一个未排序的整数数组,找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

示例

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

抛砖引玉

  • 要求算法的时间复杂度为 O(n),即限制了只能循环一次;
  • 先对数组排序
  • 循环数组记录后一个元素等于前一个元素+1或者等于前一个元素的数量
    • 满足条件++,不然重置
    • 与之前记录的值取最大值
  • 个人觉得和题目的限制,虽然排序是用数组原生的方法做的,但是应该是多了一次排序的循环
/**
 * @param {number[]} nums
 * @return {number}
 */
  var longestConsecutive = function (nums) {
      if (nums.length < 2) return nums.length;
      var _result = 1, middleValue = 1;
      nums.sort((a, b) => a - b)
      for (let index = 0; index < nums.length; index++) {
          if (nums[index] === nums[index + 1]) {
              continue // 跳出本次循环
          } else if (nums[index] + 1 === nums[index + 1]) {
              middleValue++
          } else {
              middleValue = 1
          }
          _result = Math.max(_result, middleValue);
      }
      return _result;
  };

官方答案

  • 哈希表

我们考虑枚举数组中的每个数 x,考虑以其为起点,不断尝试匹配x+1,x+2,⋯ 是否存在,假设最长匹配到了 x+y,那么以 x 为起点的最长连续序列即为 x,x+1,x+2,⋯,x+y,其长度为 y+1,我们不断枚举并更新答案即可。

对于匹配的过程,暴力的方法是O(n) 遍历数组去看是否存在这个数,但其实更高效的方法是用一个哈希表存储数组中的数,这样查看一个数是否存在即能优化至O(1) 的时间复杂度。

仅仅是这样我们的算法时间复杂度最坏情况下还是会达到)O(n2)(即外层需要枚举 O(n) 个数,内层需要暴力匹配 OO(n) 次),无法满足题目的要求。但仔细分析这个过程,我们会发现其中执行了很多不必要的枚举,如果已知有一个x,x+1,x+2,⋯,x+y 的连续序列,而我们却重新从 x+1,x+2 或者是 x+y 处开始尝试匹配,那么得到的结果肯定不会优于枚举 x 为起点的答案,因此我们在外层循环的时候碰到这种情况跳过即可。

那么怎么判断是否跳过呢?由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的,不然按照上面的分析我们会从 x−1 开始尝试匹配,因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。

var longestConsecutive = function(nums) {
    let num_set = new Set();
    for (const num of nums) {
        num_set.add(num);
    }

    let longestStreak = 0;

    for (const num of num_set) {
        if (!num_set.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;

            while (num_set.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;   
};

高手在民间

  • Set 的查找
    • Set 查找元素的时间复杂度是 O(1),JS 的 Set 能给数组去掉重复元素
    • 将数组元素存入 set 中,遍历数组 nums
    • 如果 nums[i] - 1 存在于 set ,说明 nums[i] 不是连续序列的起点,跳过,继续遍历
    • 当前项没有“左邻居”,它就是连续序列的起点
    • 不断在 set 中查看 cur + 1 是否存在,存在,则 count +1
    • cur 不再有 “右邻居” 了,就算出了一段连续序列的长度

var longestConsecutive = (nums) => {

  const set = new Set(nums) // set存放数组的全部数字
  let max = 0
  for (let i = 0; i < nums.length; i++) {
    if (!set.has(nums[i] - 1)) { // nums[i]没有左邻居,是序列的起点
      let cur = nums[i]
      let count = 1
      while (set.has(cur + 1)) { // cur有右邻居cur+1
        cur++ // 更新cur
        count++ 
      }
      max = Math.max(max, count) // cur不再有右邻居,检查count是否最大
    }
  }
  return max
}


  • 哈希表
    • 遍历原数组依次向map中存储原数组的值及其包含当前值的连续长度
    • 当前值的连续长度有两部分组成:1、小于当前值的连续长度,2、大于当前值的连续长度
    • 每次遍历结束同步map中的连续长度-供下次遍历中使用
    • 更新返回值max
var longestConsecutive = (nums) => {

  let map = new Map()
  let max = 0
  for (const num of nums) { // 遍历nums数组
    if (!map.has(num)) { // 重复的数字不考察,跳过
      let preLen = map.get(num - 1) || 0  // 获取左邻居所在序列的长度 
      let nextLen = map.get(num + 1) || 0 // 获取右邻居所在序列的长度 
      let curLen = preLen + 1 + nextLen   // 新序列的长度
      map.set(num, curLen) // 将自己存入 map
      max = Math.max(max, curLen) // 和 max 比较,试图刷新max
      map.set(num - preLen, curLen)  // 更新新序列的左端数字的value
      map.set(num + nextLen, curLen) // 更新新序列的右端数字的value
    }
  }
  return max
}


菜鸡的自白

优化说明:

  • 没有考虑到可以使用set去重所有循环中需要单独判断存在重复值的问题
  • 哈希表天然解决了重复值的问题,但是每个数据均需要统计连续长度还需要实时更新,感觉理解起来会繁琐一点
  • 个人觉得‘Set 的查找’和官方的方法是比较有意思的
/**

 * @param {number[]} nums
 * @return {number}
 */
  var longestConsecutive = function (nums) {
      if (nums.length < 2) return nums.length;
      var _result = 1;
      for (let index = 0; index < nums.length; index++) {
          if (!nums.includes(nums[index] - 1)) {
              let middleValue = nums[index];
              let currentStreak = 1;
              while (nums.includes(middleValue + 1)) {
                  middleValue += 1;
                  currentStreak += 1;
              }
              _result = Math.max(_result, currentStreak);
          }
      }
      return _result;
  };

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:坑人的小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一天一大 leet(计算右侧小于当前元素的个数)难度:困难-Day20200711

    给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质:counts[i] 的值是 nums[i] 右侧小于 nu...

    前端小书童
  • 一天一大 leet(长度最小的子数组)难度:中等 DAY-28

    给定一个含有 n 个正整数的数组和一个正整数 s,找出该数组中满足其和 ≥s 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的连续子数组,返回 0。

    前端小书童
  • 一天一大 lee(N 皇后)难度:困难-Day20200903

    n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

    前端小书童
  • 新闻接口调试

    ProsperLee
  • Python的系统管理_06_pytho

    res =subprocess.Popen(['uname','-sv'],stdout=subprocess.PIPE)

    py3study
  • ES6 新特性之 let, const : JavaScript在变量方面的改进。

    我们知道,JavaScript是没有块级作用域的,如果在块内使用var声明一个变量,它在代码块外面仍旧是可见的:

    一个会写诗的程序员
  • 最佳加法表达式

     给定n个1到9的数字,要求在数字之间最多添加m个加号(加号两边必须有数字,并且不能有两个或两个以上加号相邻),使得所得到的加法表达式的值最小,并输出该值。

    mathor
  • vue中@change兼容问题

    问题:兼容性差距,由于@change触发方式不同,导致时间加载不够统一,时间触发出现问题。

    流眸
  • es6之块级作用域

    用户1741436
  • nodejs错误:PayloadTooLargeError: request entity too large

    最近在使用Nodejs写POST接口的时候,涉及到客户端在请求体中上传base64编码图片的问题,例如我使用的POST请求,问题描述如下:

    ccf19881030

扫码关注云+社区

领取腾讯云代金券