一天一大 leet

标签: 一天一大leet  前端  leetcode  javascript

20200606

img

题目(难度:困难):

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

示例

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

抛砖引玉

img

  • 要求算法的时间复杂度为 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;
  };

博客: 小书童博客
公号: 坑人的小书童
坑人的小书童

版权声明:本文为gaowenju1991原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/gaowenju1991/article/details/106586510

智能推荐

【Spark 内核】 Spark 内核解析-下

Spark内核泛指Spark的核心运行机制,包括Spark核心组件的运行机制、Spark任务调度机制、Spark内存管理机制、Spark核心功能的运行原理等,熟练掌握Spark内核原理,能够帮助我们更好地完成Spark代码设计,并能够帮助我们准确锁定项目运行过程中出现的问题的症结所在。 Spark Shuffle 解析 Shuffle 的核心要点 ShuffleMapStage与ResultSta...

Reflect反射的基础知识

写个父类: 写个子类: 利用反射获得该子类中的属性,方法,构造,父类及接口: 运行结果:...

spring cloud netflix (07) 服务的消费者(feign)

前言 完整知识点:spring cloud netflix 系列技术栈 Feign (同步通信 HTTP通信) feign是基于接口完成服务与服务之间的通信的 搭建Feign服务 项目结构 项目搭建 pom.xml application类 application.yml 使用feign完成服务与服务之间的通信 feign是基于接口完成服务与服务之间的通信的...

AtCoder Beginner Contest 174 E.Logs

AtCoder Beginner Contest 174 E.Logs 题目链接 到最后才发现是二分,菜菜的我/(ㄒoㄒ)/~~ 我们直接二分 [1,max{a[i]}][1,max\lbrace a[i]\rbrace][1,max{a[i]}] 即可,对每一个 midmidmid,每个数 a[i]a[i]a[i] 只需要切 a[i]−1mid\frac{a[i]-1}{mid}mi...

小程序基础与实战案例

小程序开发工具与基础 小程序开发准备: 申请小程序账号( appid ) 下载并安装微信开发者工具 具体步骤如下: 先进入 微信公众平台 ,下拉页面,把鼠标悬浮在小程序图标上 然后点击 小程序开发文档 照着里面给的步骤,就可以申请到小程序账号了。 然后就可以下载 开发者工具 了 下载完打开后的界面就是这个样子 下面让我们来新建一个小程序开发项目: 在AppID输入自己刚刚注册的AppID就可以,或...

猜你喜欢

VMware centOS7 下通过minikube部署Kubernetes

1、环境准备: VMware CentOS-7-x86_64 CPU:2*2core 内存:8G 宿主机和虚拟机需网络互通,虚拟机外网访问正常 Centos发行版版本查看:cat /etc/centos-release root用户操作 2、禁用swap分区 Kubernetes 1.8开始要求关闭系统的Swap,可暂时关闭或永久禁用, 使用 $ free -m 确认swap是否为开启状态 $ s...

逻辑回归与scikit-learn

欢迎关注本人的微信公众号AI_Engine LogisticRegression 算法原理 一句话概括:逻辑回归假设数据服从伯努利分布,通过极大化似然函数(损失函数)的方法,运用梯度下降或其他优化算法来求解参数,来达到将数据二分类的目的。 定义:逻辑回归(Logistic Regression)是一种用于解决二分类(0 or 1)问题的机器学习方法,用于估计某种事物的可能性(不是概率)。比如某用户...

指针OR数组?用他们来表达字符串又有何不同?

cocowy的编程之旅 在学习C语言的过程中我们经常可以看到或者听到这样一句话:数组其实等价于指针,例如: 在这里可以轻松的看出输出后他们的值相等,其实在计算机内存里面,p为本地变量,有着他自己的作用域。而指针变量q保存着这个数组的首地址,通过*号指向这个地址保存的变量值。 然而我们再看一个例子: 这个时候计算机报错,这是为什么呢? 其实原因很简单,指针说指向的这个字符串的地址是位于计算机代码段地...

广度搜索

广度搜索的基本使用方法 广度搜索不同于深度搜索,是一种一步一步进行的过程,每一个点只记录一遍。需要用到队列记录每一步可以走到的位置,找到目标位置输出步数即可。 用到的知识:结构体、队列 如图 首先我们需要定义一个结构体来存储每个遍历到的点和步数 广搜不会用到递归,所以可以直接在主函数里写,这里需要定义一个结构体队列 初始化队列并将起始点入列 遍历 完整代码...

NIO Socket 编程实现tcp通信入门(二)

1、NIO简介 NIO面向通道和缓冲区进行工作,数据总是从通道读取到缓冲区中,或者从缓冲区写入到通道中。可以双向传输数据,是同步非阻塞式IO。NIO还引入了选择器机制,从而实现了一个选择器监听多个底层通道,减少了线程并发数。用NIO实现socket的Tcp通信需要掌握下面三个知识点: Buffer 缓冲区 Channel 通道 Selector 选择器   2、java.nio.Buff...