“This is the 11th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Record 1 algorithm problem

Longest continuous sequence – and lookup set

Leetcode-cn.com/problems/lo…

Given an out-of-order array, return the number of longest consecutive numbers in the array.

For example, [100,4,200,1,3,2], the longest consecutive number is 1,2,3,4. So return 4.

one

It is possible to pass in an empty array, so make a length judgment at the beginning.

two

There will be some duplicate numbers in it, so it will simply use an object for de-duplication.

    if(set[item]) continue
    set[item] = true.Copy the code

three

How do I get the answer when I only go through it once.

Most of these set problems can be solved by looking up sets. The main idea is to collect each number and create a collection for it. When it comes to adjacent numbers, it collects them into its own collection. In this case, there are two cases: 1. Merge with the set with only one number. 2. Merge with collections that have multiple numbers, such as [1,2] and [3,4]. So we need to record the level of each set, from the high level to the low level.

In order to create an intersection between numbers as a judgment point for merging within each loop, we need to make connections between adjacent numbers. The way to do this is to generate not only the set of the current number, but also the set of the number before the current number, that is, prev.

With this prev in place, we can determine if the current number has a collection when we iterate, so we can inherit it or create it.

Then the strategy for preV is to merge with the current set of numbers for the previous cycle if the preV already exists. If not, create a collection of preVs.

four

Since arrays are discontinuous, we need to set up a mapping of numbers and subscripts of the collection list.

And the subscript of the list of look-up sets is the same as the traversal I.

implementation

    function longestConsecutive(nums) {
        const len = nums.length
        if (len === 0) return 0
        / / to heavy
        const set = {}
        / / map
        const map = {}
        // Check the collection list
        const parent = Array.from(new Array(len), (_, i) = > i)
        // Level array
        const size = new Array(len).fill(1)
        
        for(let i = 0; i < len; i++) {
            const item = nums[i]
            const prev = item - 1
            / / to heavy
            if (set[item]) continue
            set[item] = true
            
            if(map[item] ! = =undefined) {
                // Inherits the collection, which is associated with the prev left by other numbers
                / / + 1
                const a = parent[i] = find(parent, map[item])
                size[a]++
            } else {
                // Create a collection that points to itself
                map[item] = i
            }
            
            if(map[prev] ! = =undefined) {
                // Compare the set level, merge the small size, and then expand the size
                const a = parent[i]
                const b = find(parent, map[prev])
                if (size[b] > size[a]) {
                    const t = a
                    a = b
                    b = t
                }
                
                parent[b] = a
                size[a] += size[b]
            } else {
                // Create a collection that points to itself
                map[prev] = i
            }
        }
        
        return Math.max(... size) }function find(parent, i) {
        if(parent[i] ! == i) { parent[i] = find(parent, parent[i]) }return parent[i]
    }
Copy the code

Hash table solution

Idea is a traversal of the array are collected, by the way to heavy, and then traverse again, cycle for each number of + 1, and counting, stop until there is no serial number, go to the next number.

The detail of the optimization is that when we get a number, if it has the previous number, that means it’s not the starting point of the sequence, so skip it.

    function longestConsecutive(nums) {
        if (nums.length === 0) return 0
        const map = {}
        // The key value is the same. You can also use Set.
        for (let i = 0; i < nums.length; i++) {
          const a = nums[i]
          map[a] = a
        }

        let count = 1
        // Iterate over the duplicated object
        const keys = Object.keys(map)
        for (let i = 0; i < keys.length; i++) {
          let a = map[keys[i]]
          // When there is no previous one,
          // the description is the beginning of a continuous sequence,
          // incrementing, counting
          if (map[a - 1] = =undefined) {
            let _count = 0
            while(map[a] ! = =undefined) {
              _count++
              a++
            }
            
            // Compare the largest in history
            count = Math.max(count, _count)
          }
        }

        return count
    }
Copy the code

The end of the