This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 Hello everyone, I am Xiao Cheng, a sophomore front-end enthusiast

📢 This article will cover collections in data structures

📢 Thank you very much for reading

📢 May you be true to yourself and love life

💡 Knowledge points look first

  • What is a set?
  • What are the methods of the set
  • Implement a collection
  • How collections operate
  • LeetCodeIn actual combat

📢 twitter

In the previous article, we learned 3 kinds of linear structure, next we need to learn the set, I prefer to call it a container, it has a very powerful method and efficiency, let’s learn ~

What is a set?

A set is a set of unordered and unique (that is, unrepeatable) items that have the properties of a finite set in mathematics.

In mathematics, a set is a group of different objects, such as:

Set of natural numbers: N = {0, 1, 2, 3, 4, 5, 6… }, objects in the collection are surrounded by curly braces

The figure above can represent a set that is unique and disordered

Let’s implement a collection together

What are the methods of collection?

In ES6, we added a new Set class that allows you to quickly create a collection. Here we implement a Set class ourselves

Above we said that we use an object to create collections (or arrays)

Of course, it’s easier to select objects for creation. JavaScript objects don’t allow a key to point to two different properties, which ensures that the elements in the collection are unique

Here we need to add these methods to the collection

methods meaning
add(value) Adds a new element to the collection
remove(value) Removes a value from the collection
has(value) Determines whether a value exists in the set
clear() Empty the collection
size() Returns the number of elements in the collection
values() Returns an array of all values in the collection

Three, handwriting to achieve a collection

Create a Set class

Create a collection using objects

class Set {
    constructor () {
        this.data = {}
    }
}
Copy the code

Next, encapsulate the method

Implement the HAS method

Before you can implement the Add method, you need to implement a HAS method

has(value) {
    return value in this.data
}
Copy the code

Here we use the in operator to determine whether value exists in the data object and return true if so

3. Implement add method

Due to the uniqueness of the set, we need to judge whether the current element exists in the current set before adding elements. If not, add it to the set and return true with success; if there is, return false without addition

add(value) {
    if(!this.has(value)) {
        this.data[value] = value
        return true
    }
    return false
}
Copy the code

Here we use the has method first to determine whether there is a value, if not, to add to the collection

4. Implement the remove method

The remove method removes an element from the collection and takes as an argument the element to be removed

remove (value) {
    if(this.has(value)) {
        delete this.data[value]
        return true
    }
    console.log('Element to delete not found');
    return false
}
Copy the code

In this case, the has method is used to determine whether there is this value. If there is, the element is deleted by delete. There is no hint that the element is not found

5. Implement clear method

The clear method clears the entire collection, which can also be done by resetting the object

clear() {
    this.data = {}
}
Copy the code

6. Implement size method

There are many ways to implement size

The first kind of

You can use keys, the built-in method of the Object class, which returns an array of all the properties of a given object

So we can use the length method to get its length

size() {
    return Object.keys(this.data).length
}
Copy the code

The second,

We can manually extract every attribute on a data object, recording the number of attributes

size() {
    let count = 0;
    // Iterate over the object
    for(let prop in this.data) {
        if(this.data.hasOwnProperty(prop)) {
            ++count
        }
    }
    return count
}
Copy the code

Here we also need to use the object’s hasOwnProperty method to determine if this property is a prototypical method, because the object class contains many built-in methods that use for-in traversal to reach values that are not in the collection

It’s easy to use the first method

7. Values method

We need to convert the data set into an array, and we can do that using the keys method we used before

values() {
    return Object.keys(this.data)
}
Copy the code

8. Complete Set implementation

class Set {
    constructor() {
        this.data = {}
    }
    has(value) {
        return value in this.data
    }
    add(value) {
        if (!this.has(value)) {
            this.data[value] = value
            return true
        }
        return false
    }
    remove(value) {
        if (this.has(value)) {
            delete this.data[value]
            return true
        }
        console.log('Element to delete not found');
        return false
    }
    clear() {
        this.data = {}
    }
    size() {
        return Object.keys(this.data).length
    }
    values() {
        return Object.keys(this.data)
    }
}
Copy the code

9. How to use the Set method

We just need to construct an instance object with the new method to manipulate it

const set = new Set(a)Copy the code

Add elements

set.add(2)
set.add(3)
Copy the code

Remove elements

set.remove(3)
set.remove(4) // The element to delete was not found
Copy the code

4. Set operation method

In mathematics, we often do some operations to find the intersection, find the union, find the subset difference, here we can also achieve

methods meaning
union() And set
intersection() intersection
difference() Difference set
subset() Difference set

1. Perform the union operation

A union is a set of two sets given, the new set of all the elements

How do you do that

  1. First we need to receive an incoming collectionotherSetAnd create a new collection to hold the final data
  2. throughvaluesMethod expands the collection into an array, and traversals are added to the new collection, as well as to the array passed in
  3. Finally return the new collection

Note that since we encapsulate values without a reservation parameter, we need to use otherSet. Values when we convert otherSet

union(otherSet) {
    const unionSet = new Set(a)// Set -> array
    const values = this.values()
    const values2 = otherSet.values(otherSet)
    values.map(item= > { unionSet.add(item) })
    values2.map(item= > { unionSet.add(item) })
    return unionSet
}
Copy the code

How do you use it?

const set = new Set(a)const set2 = new Set()
set2.add(3)
set.add(2)
console.log(set.union(set2)); // Set { data: { '2': '2', '3': '3' } }
Copy the code

2. Implement intersection operations

The intersection operation is to return a new set of the same elements in two sets

Implementation approach

  1. Create a new collection to return and receive a collection at the same time
  2. Again, it’s an array to operate on
  3. You take one set and you iterate over it, and you use the elements in the other sethasTo see if it’s in another set, if it’s in a common set, add it to the new set

Do you know the time complexity of this implementation?

intersection() {
    const intersectionSet = new Set(a)// The current collection is converted to an array
    const values = this.values()
    for (let i = 0; i < values.length; i++) {
        if (otherSet.has(values[i])) {
            intersectionSet.add(values[i])
        }
    }
    return intersectionSet

Copy the code

3. Implement the difference set operation

The difference set operation returns the relatively different parts, and the difference set of A and B is the separate part of A

The blue one is what we want

Realize the idea, and find the union can be the opposite

difference(otherSet) {
    const differenceSet = new Set(a)const values = this.values
    for (let i = 0; i < values.length; i++) {
        OtherSet = otherSet = otherSet = otherSet
        if(! otherSet.has(values[i])) { differenceSet.add(values[i]) } }return differenceSet
}
Copy the code

4. Implement the subset method

Subset is to determine whether they’re parent-child, whether A subset is part of B

Implementation approach

  • If the set A is larger than the set B, it cannot be A subset
  • Determine if all of the elements in set A are found in set B
subset(otherSet) {
    if (this.size() > otherSet.size()) {
        return false
    }
    / / return the interrupt
    let values = this.values()
    for(let i = 0; i<values.length; i++) {if(! otherSet.has(values[i])) {return false}}return true
}
Copy the code

Up to now! Finally implemented these methods, in fact, the idea is the same, thank you very much to see here, thank you ~

Five, LeetCode actual combat

349. Intersection of two arrays

Given two arrays, write a function to calculate their intersection.

Input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2]

When LeetCode brushes up, we don’t need to implement a collection ourselves, we can create a collection directly using the existing Set class

AC elegant code

var intersection = function (nums1, nums2) {
    // delete nums1
    const set1 = new Set(nums1)
    const set2 = new Set(nums2)
    return [...new Set([...set1].filter(item= > set2.has(item)))]
};
Copy the code

It may not be the same as the previous one, because there are a lot of apis in the array that we can use, and we need to be able to make choices for different scenarios

📖 summary

In this article, we encapsulate a collection and realize the operation methods of many collections.

In ES6 new Set class, its bottom layer is to achieve through map, map bottom layer using hash table to achieve, it greatly optimize the speed of our search value, so in the brush problem, you can think about whether to use Set to achieve.

That’s the end of this article on collections, which I’m sure you’ll learn a lot from. The next article will take you through the mysteries of dictionaries.

You are welcome to follow this column and stay tuned for the latest articles

The rest of this column

Stack 👉 what is a stack? Handwriting a stack structure!

Queue 👉 [Untangle data structures] Turn on data structures and algorithms from here

Linked list 👉 [dissolve data structure] explain linked list structure in detail, and implement a linked list

Finally, I may not be clear enough in many places, please forgive me

💌 if the article has any mistakes, or have any questions, welcome to leave a message, also welcome private letter exchange