JavaScript算法46- 最长连续序列（leetCode:128middle）

128. 最长连续序列

一、题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例

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

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

二、题解

初版

栗子： [100,4,200,200,1,3,2]
思路：

1. 原数组从小到大排序 [1,2,3,4,100,200,200]
2. 去重 [1,2,3,4,100,200]
3. 找出连续片段 [1,2,3,4] [100,200]
4. 取最长 [1,2.,3,4] ? 4

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if(nums.length < 2) return nums.length;
    // 排序 + 去重
    const orderNums = [...new Set(nums.sort((a,b)=>a-b))];
    let maxLength = 1;
    let curLength = 1;
    for(let i = 1; i< orderNums.length; i++){
        if((orderNums[i]-orderNums[i-1]) === 1){
            curLength++;
        }else{
            maxLength = Math.max(maxLength,curLength);
            curLength = 1;
        }
    }
    return Math.max(maxLength,curLength);
};

优化版

优化点：相较于初版，少了排序
栗子： [100,4,200,200,1,3,2]
思路：

1. 去重 [100,4,200,1,3,2]
2. 找出连续片段的起点值（即数组中不存在这个值-1） 起点值1、100
3. 继而得到完整片段 [1,2,3,4] [100,200]
4. 比较各个片段的长度，得到最大值 [1,2.,3,4] ? 4

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if(nums.length < 2) return nums.length;
    // 去重
    const numsSet = new Set(nums);
    let maxLength = 1;
    for(const num of numsSet){
        if(!numsSet.has(num-1)){
            let curNum = num;
            let curLength = 1;
            while(numsSet.has(curNum + 1)){
                curNum++;
                curLength++;
            }
            maxLength = Math.max(maxLength,curLength);            
        }
    }
    return maxLength;
};

三、补充

Math.max()

返回输入参数的最大数字，如果没有参数，则返回 -Infinity。（参数可以是多个）
语法：Math.max(value0, value1, /* … ,*/ valueN)
详情参考：Math.max()

// case1
const array1 = [1, 3, 2];
console.log(Math.max(...array1)); // 3

// case2
console.log(Math.max(-1, -3, -2)); // -1

集合 Set

Set详解
集合（set）中的元素只会出现一次，可以按照插入顺序迭代集合中的元素。

构造函数
Set()

const mySet= new Set();

const mySet= new Set([1, 2, 3, 4, 5]);

属性
size

mySet.size; // 5

方法
add()

mySet.add(10)

delete()

console.log(mySet.delete(1)); // true
console.log(mySet.delete(20)); //false 集合中没有要删的值

clear()

mySet.clear();
console.log(mySet()); // Set(0) {size: 0}

has()

console.log(mySet.has(1)); // true

console.log(mySet.has(99)); // false

---

values()
返回一个新的集合迭代器对象，该对象包含此集合对象中每个元素的值，按插入顺序排列。

keys()
keys() 返回一个迭代器，其值为集合中的所有键名。
如果是数组，返回的是索引；如果是Set集合，返回的是值（Set的值被同时用作键和值）。

const mySet = new Set();
mySet.add("foo");
mySet.add("bar");
mySet.add("baz");

const setIter = mySet.keys();

console.log(setIter.next()); // { value: 'foo', done: false }
console.log(setIter.next());  // { value: 'bar', done: false }
console.log(setIter.next()); // { value: 'baz', done: false }

---

entries()
此方法返回一个新的集合迭代器对象，该对象包含了此集合中每个元素的[value, value]数组，按插入顺序排列。
注：Set 对象没有类似于 Map 对象中的 key，为了保持 API 与 Map 对象类似，这里每个 entry 的 key 和 value 都相同，所以返回的数组为 [value, value]。

forEach()
语法

• forEach(callbackFn)
• forEach(callbackFn, thisArg)

// 方式一
function logSetElements(value1, value2, set) {
  console.log(`s[${value1}] = ${value2}`);
}

new Set(['foo', 'bar', undefined]).forEach(logSetElements);
// s[foo] = foo
// s[bar] = bar
// s[undefined] = undefined

// 方式二
new Set(['foo', 'bar', undefined]).forEach((value1, value2, set) => {
    console.log(`s[${value1}] = ${value2}`);
})
// s[foo] = foo
// s[bar] = bar
// s[undefined] = undefined

迭代器和生成器

迭代器

迭代器是一个对象，它定义了一个序列，通过使用next()方法迭代任何一个对象，
该方法返回的对象包含两个属性 {value:xxx, done:false}

• value：迭代序列的下一个值
• done： 如果已经迭代到序列的最后一个值，则为true

const mySet = new Set();
mySet.add("foo");
mySet.add("bar");
mySet.add("baz");

const setIter = mySet.keys();

console.log(setIter.next()); // { value: 'foo', done: false }
console.log(setIter.next());  // { value: 'bar', done: false }
console.log(setIter.next());  // { value: 'baz', done: false }
console.log(setIter.next());  // { value: undefined, done: true }
console.log(setIter.next());  // { value: undefined, done: true }              

可迭代对象

若一个对象拥有迭代行为，比如在for…of …中会循环一些值，那么这个对象便是一个可迭代对象。在ES6中，所有的集合对象（数组、Set集合及Map集合）和字符串都是可迭代对象，可迭代对象都绑定了默认的迭代器，而其它类型（比如Object）则没有。

1. 访问默认迭代器

• 可迭代对象，都有一个Symbol.iterator方法，for-of循环时，通过调用Symbol.iterator方法来获取默认迭代器的，这一过程是在JavaScript引擎背后完成的。
• 可以主动获取一下这个默认迭代器来感受一下：

// 迭代字符串
const myString = 'abcdef';

// 方式一
const setIter2 = myString[Symbol.iterator](); 
console.log(setIter2.next()); // { value: 'a', done: false }
console.log(setIter2.next()); // { value: 'b', done: false }
console.log(setIter2.next()); // { value: 'c', done: false }

// 方式二
for(let char of myString) {
    console.log(char)
}
// a
// b
// c
// d
// e
// f

2. 内建迭代器

• ES6中的集合对象，数组、Set集合和Map集合，都内建了三种迭代器：
• entries() 返回一个迭代器，其值为多个键值对。
  如果是数组，第一个元素是索引位置；如果是Set集合，第一个元素与第二个元素一样，都是值。
• values() 返回一个迭代器，其值为集合的值。
• keys() 返回一个迭代器，其值为集合中的所有键名。
  如果是数组，返回的是索引；如果是Set集合，返回的是值（Set的值被同时用作键和值）。

// 迭代数组
const myArray = [1,8,5,7,6,];
const setIter1 = myArray.values();
console.log(setIter1.next()); // { value: 1, done: false }
console.log(setIter1.next()); // { value: 8, done: false }
console.log(setIter1.next()); // { value: 5, done: false }

生成器

生成器是一种返回迭代器的函数，通过function关键字后的星号（*）来表示，函数中会用到新的关键字yield。

function *createIterator(items) {
    for(let i=0; i<items.length; i++) {
        yield items[i];
    }
}

let iterator = createIterator([1, 2, 3]);

// 既然生成器返回的是迭代器，自然就可以调用迭代器的next()方法
console.log(iterator.next());  // "{ value: 1, done: false}"
console.log(iterator.next());  // "{ value: 2, done: false}"
console.log(iterator.next());  // "{ value: 3, done: false}"
console.log(iterator.next());  // "{ value: undefiend, done: true}"
// 之后所有的调用都会返回相同内容
console.log(iterator.next());  // "{ value: undefiend, done: true}"

上面，我们用ES6的生成器，大大简化了迭代器的创建过程。我们给生成器函数createIterator()传入一个items数组，函数内部，for循环不断从数组中生成新的元素放入迭代器中，每遇到一个yield语句循环都会停止；每次调用迭代器的next()方法，循环便继续运行并停止在下一条yield语句处。
生成器的创建方式

生成器是个函数

function *createIterator(items) { ... }

也可以用函数表达式方式书写

let createIterator = function *(item) { ... }

也可以添加到对象中，ES5风格对象字面量：

let o = {
    createIterator: function *(items) { ... }
};

let iterator = o.createIterator([1, 2, 3]);

ES6风格的对象方法简写方式：

let o = {
    *createIterator(items) { ... }
};

let iterator = o.createIterator([1, 2, 3]);