Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

947. Removal of the largest number of stones in the same row or row

N stones are placed at integer coordinate points in a two-dimensional plane. There can be no more than one stone on each coordinate point.

A stone can be removed if there are other stones in the same row or row as a stone.

Stones [I] = [xi, yi]; stones[I] = [xi, yi];

 

Example 1:

Input: featuring = [[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2]] output: 5: a way to remove the five stone is as follows: 1. Remove stone [2,2] as it walks with stone [2,1]. 2. Remove rock [2,1] as it is in the same column as [0,1]. 3. Remove stone [1,2] as it walks with [1,0]. 4. Remove the stone [1,0] as it is in the same column as [0,0]. 5. Remove the rock [0,1] as it runs with [0,0]. The stone [0,0] cannot be removed because it is not in line/column with another stone.Copy the code

Example 2:

Stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] Remove stone [2,2] as it walks with stone [2,0]. 2. Remove rock [2,0] as it is in the same column as [0,0]. 3. Remove the rock [0,2] as it runs with [0,0]. Stones [0,0] and [1,1] cannot be removed because they are not in line/column with another stone.Copy the code

Example 3:

Input: stones = [[0,0]] Output: 0 Explanation: [0,0] is the only stone on the plane, so it cannot be removed.Copy the code

 

Tip:

  • 1 <= stones.length <= 1000
  • 0 <= xi, yi <= 104
  • There are no two stones on the same coordinate point

Train of thought

  1. This problem is also a more typical and search set of problems, similar to the number of provinces we did before the problem;
  2. If we want to eliminate it the way we did last time, then we need to iterate over the maximum coordinates, and then build up an array of coordinates;
  3. So we can do the same thing we did last time with the number of provinces, but we’re going to do it with a set lookup;
  4. Walk through the pile, using two at a timemapRecord rows and columns to see if any of the same rows appear before;
  5. If any, establish a relationship between the two stones;
  6. Traverse the stone pile again and judge how many are related to the number of records can be returned.

implementation

/ * * *@param {number[][]} stones
 * @return {number}* /
var removeStones = function(stones) {
    const n = stones.length;
    const uf = new UnionFind(n);

    let rowMap = new Map(), colMap = new Map(a);// The first loop is traversed to establish the relationship
    for (let i = 0; i < n; i++) {
        const [ row, col ] = stones[i];
        // There are stones in the same row, marked together
        if (rowMap.has(row)) {
            uf.merge(i, rowMap.get(row));
        }

        // There are stones in the same row, marked together
        if (colMap.has(col)) {
            uf.merge(i, colMap.get(col));
        }

        // Record each row and each column
        rowMap.set(row, i);
        colMap.set(col, i);
    }

    // run the following command to find the collection
    let result = 0;
    let set = new Set(a);// If there are rows or columns, the description can be deleted; if there are no rows or columns, the description can be added
    for (let i = 0; i < n; i++) {
        let index = uf.find(i);
        if (set.has(index)) {
            result++;
        } else{ set.add(index); }}return result;
};

class UnionFind {
  constructor(n) {
    // The parent of each element is itself
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find the parent of the element
  find(index) {
    return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
  }

  // Set the parent of index2 to the parent of index1
  merge(index1, index2) {
    this.parent[this.find(index2)] = this.find(index1); }}Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.