一道算法题(JS)-寻找数组中最大连续序列

栏目: 编程工具 · 发布时间: 5年前

内容简介:给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为输入:[100, 4, 200, 1, 3, 2]解释:最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

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

示例:

输入:[100, 4, 200, 1, 3, 2]

输出: 4

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

思路

  • 连续序列,首先要对传入数组进行 排序
  • 连续序列的标志为 s[n] - s[n-1] === 1 ,针对这个来进行循环判断
  • 定义循环中的最大长度 num 以及最终长度 max ,每次需取 max(num, max)
  • 当 s[n] - s[n-1] !== 1 时,及连续序列断开,需重置当前最大长度
  • 特殊用例情况:[1,2,2,3]中的连续序列为[1,2,3],长度为3。因此在循环中当s[n] === s[n-1]时候,应跳过

直接上代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
  if (!nums.length) return 0;
  var sortedNums = nums.sort((a,b) => (a - b));
  
  var i = 1;
  var num = 1;
  var max = 1;
  while(i < sortedNums.length) {
    if (sortedNums[i] - sortedNums[i - 1] === 1) {
      num++;
    } else if (sortedNums[i] === sortedNums[i - 1]) {
      i++;
      continue;
    } else {
      num = 1;
    }
    max = Math.max(max, num);
    
    i++;
  }
  
  return max
};
复制代码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

触动人心

触动人心

Josh Clark / 包季真 / 电子工业出版社 / 2011-10 / 79.00元

本书是《Tapworthy: Designing Great iPhone Apps》的中文翻译版。 可能你设计网站产品或软件界面早已得心应手,可是遇到了iPhone,却感觉无从下手。 无论你是产品经理、设计师、创业者还是程序员,本书都能告诉你如何从iPhone的角度来思考应用设计。本书能帮助你理解如何设计iPhone应用,要创建一款触动人心的应用,需要如何去综合思考设计、心理、文化、......一起来看看 《触动人心》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换