Set structure

Introduce a,

A collection is usually composed of an unordered set of elements that cannot be repeated. The elements of a mathematical set are repeatable, but the elements of a computer set are not.

Collections are special arrays.

• What is special is that the elements are not sequential and cannot be repeated.
• No order means no access through subscripts, and no repetition means that only one copy of the same object will exist in the collection.

Second, the realization of collection

A more common implementation of collections is a hash table, which is encapsulated using JavaScript Object

Collection of common operations

• add(value)Adds a new item to the collection
• remove(value)Removes a value from the collection
• has(value)Returns if the value is in the collectiontrueOtherwise return false
• clear()Removes all items from the collection
• size()Returns the number of elements contained in the collection. With an array oflengthProperties similar to
• values()Returns an array containing all the values in the collection.
• There are other ways to do it, not so much, but there’s no encapsulation

1.Set class code implementation

function MySet() {
  this.items = {};

  MySet.prototype.add = function (value) {
    if (this.has(value)) return false;
    this.items[value] = value;
    return true;
  };

  MySet.prototype.has = function (value) {
    return this.items.hasOwnProperty(value);
  };

  MySet.prototype.remove = function (value) {
    if (!this.has(value)) return false;
    delete this.items[value];
    return true;
  };

  MySet.prototype.clear = function () {
    this.items = {};
  };

  MySet.prototype.size = function () {
    return Object.keys(this.items).length;
  };

  // Returns an array containing all the values in the collection
  MySet.prototype.values = function () {
    return Object.keys(this.items);
  };
}
Copy the code

The test code

// Test the code
var set = new MySet();
console.log(set.add("10")); // true
console.log(set.add("10")); // false
console.log(set.add("20")); // true
console.log(set.add("30")); // true
console.log(set.values()); // ['10', '20', '30']

console.log(set.remove("10")); // true
console.log(set.remove("10")); // false
console.log(set.values()); // ['20', '30']
console.log(set.size()); / / 2
Copy the code

2. Encapsulation of inter-set operations

• Union: For a given set of two sets, a new set containing all the elements of both sets is returned
• Intersection: For a given set of two sets, returns a new set containing elements in both sets
• Difference set: For a given set of two sets, return a new set containing all elements that exist in the first set and not in the second
• Subset: Verifies whether a given set is a subset of another set

2.1 Implementation of union

// merge ==> Merge two sets
MySet.prototype.union = function (otherSet) {
  // Create a new set
  var unionSet = new MySet();
  // Retrieve the value of the current set
  var values = this.values();

  // Add the value from the current set to the new set
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i]);
  }

  // Retrieve the set passed in
  values = otherSet.values();
  // Add the incoming set to the new set
  for (var i = 0; i < values.length; i++) {
    // Duplicate content is filtered out because it is a set structure
    unionSet.add(values[i]);
  }

  return unionSet;
};
Copy the code

The test code

// Test the code
var set1 = new MySet();
var set2 = new MySet();
set1.add("10");
set1.add("20");
set1.add("30");

set2.add("10");
set2.add("40");
set2.add("50");
var unionSet = set1.union(set2);
console.log(unionSet.values()); // ['10', '20', '30', '40', '50']
Copy the code

2.2 Realization of intersection

// intersection ==> Fetch the duplicate contents of two sets
MySet.prototype.intersect = function (otherSet) {
  var intersectSet = new MySet();
  var values = this.values();

  for (var i = 0; i < values.length; i++) {
    // Find duplicates
    if (otherSet.has(values[i])) {
      // Add the duplicate content to the crosssetintersectSet.add(values[i]); }}return intersectSet;
};
Copy the code

The test code

var intersectSet = set1.intersect(set2);
console.log(intersectSet.values()); / / / '10'
Copy the code

2.3 Implementation of difference set

// Set difference ==> In contrast to the intersection, eliminate the contents of set A that also exist in set B
MySet.prototype.difference = function (otherSet) {
  var differenceSet = new MySet();
  var values = this.values();
  for (var i = 0; i < values.length; i++) {
    if (!otherSet.has(values[i])) {
      differenceSet.add(values[i]);
    }
  }
  return differenceSet;
};
Copy the code

The test code

var differenceSet = set1.difference(set2);
console.log(differenceSet.values()); // ['20', '30']
Copy the code

2.4 Determine the implementation of subsets

// Subset ==> If everything in set B exists in set A, then B is A subset of A
MySet.prototype.subset = function (otherSet) {
  var values = this.values();
  for (var i = 0; i < values.length; i++) {
    if(! otherSet.has(values[i])) {return false; }}return true;
};
Copy the code

The test code

console.log(set1.subset(set2)); // false
Copy the code

3. Complete code

function MySet() {
  this.items = {};

  MySet.prototype.add = function (value) {
    if (this.has(value)) return false;
    this.items[value] = value;
    return true;
  };

  MySet.prototype.has = function (value) {
    return this.items.hasOwnProperty(value);
  };

  MySet.prototype.remove = function (value) {
    if (!this.has(value)) return false;
    delete this.items[value];
    return true;
  };

  MySet.prototype.clear = function () {
    this.items = {};
  };

  MySet.prototype.size = function () {
    return Object.keys(this.items).length;
  };

  // Returns an array containing all the values in the collection
  MySet.prototype.values = function () {
    return Object.keys(this.items);
  };

  // merge ==> Merge two sets
  MySet.prototype.union = function (otherSet) {
    // Create a new set
    var unionSet = new MySet();
    // Retrieve the value of the current set
    var values = this.values();

    // Add the value from the current set to the new set
    for (var i = 0; i < values.length; i++) {
      unionSet.add(values[i]);
    }

    // Retrieve the set passed in
    values = otherSet.values();
    // Add the incoming set to the new set
    for (var i = 0; i < values.length; i++) {
      // Duplicate content is filtered out because it is a set structure
      unionSet.add(values[i]);
    }

    return unionSet;
  };

  // intersection ==> Fetch the duplicate contents of two sets
  MySet.prototype.intersect = function (otherSet) {
    var intersectSet = new MySet();
    var values = this.values();

    for (var i = 0; i < values.length; i++) {
      // Find duplicates
      if (otherSet.has(values[i])) {
        // Add the duplicate content to the crosssetintersectSet.add(values[i]); }}return intersectSet;
  };

  // Set difference ==> In contrast to the intersection, eliminate the contents of set A that also exist in set B
  MySet.prototype.difference = function (otherSet) {
    var differenceSet = new MySet();
    var values = this.values();
    for (var i = 0; i < values.length; i++) {
      if (!otherSet.has(values[i])) {
        differenceSet.add(values[i]);
      }
    }
    return differenceSet;
  };

  // Subset ==> If everything in set B exists in set A, then B is A subset of A
  MySet.prototype.subset = function (otherSet) {
    var values = this.values();
    for (var i = 0; i < values.length; i++) {
      if(! otherSet.has(values[i])) {return false; }}return true;
  };
}

// Test the code
var set1 = new MySet();
var set2 = new MySet();
set1.add("10");
set1.add("20");
set1.add("30");

set2.add("10");
set2.add("40");
set2.add("50");
var unionSet = set1.union(set2);
console.log(unionSet.values()); // ['10', '20', '30', '40', '50']

var intersectSet = set1.intersect(set2);
console.log(intersectSet.values()); / / / '10'

var differenceSet = set1.difference(set2);
console.log(differenceSet.values()); // ['20', '30']

console.log(set1.subset(set2)); // false

Copy the code

Three, the application

1.Intersection of two arrays

/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}* /
var intersection = function (nums1, nums2) {
  // With the set structure, a line of code can be used
  return [...new Set(nums1)].filter(n= > nums2.includes(n))
};
Copy the code