前端刷题路-Day30：省份数量（题号547）-一一网

省份数量（题号547）

题目

有n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，那么城市a与城市c间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个n x n的矩阵isConnected，其中isConnected[i][j] = 1表示第i个城市和第j个城市直接相连，而isConnected[i][j] = 0表示二者不直接相连。

返回矩阵中省份的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
复制代码

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
复制代码

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

链接

leetcode-cn.com/problems/nu…

解释

这题和岛屿问题其实差不多，就是理解题目意思上有点费劲，笔者反正是花了不少时间才理解了题目的真正含义。

岛屿问题的一个坐标[i, j]其实都是一个独立的元素，但在这题中，每个坐标代表的不是独立的元素，而是一个关系，真正的元素只有n个，因为题目说了这是一个n*n的矩阵。

比方说点[1, 4]，那就证明城市1和城市4其实是有关系的，它们属于一个省份，所以会被关联起来。

这样一来题目就简单了一些，写法上倒是没有什么太大的问题，问题主要有两个?：

并查集的变种（数组形态）
性能差异

先看看第一点，由于现在元素的个数只有n个，所以可以使用数组，利用数组的index和value来确定一个数组的自身内容和其parent，最后只需要获取index和value相等的元素即可。

第二点的话需要具体看代码说了，这里单纯说说不清楚。

?看看代码：

自己的答案（泛洪算法）

说实话，泛洪算法在这里其实也是管用的，只是需要注意泛洪的范围并不是周围的，而是i和j相同的元素，对应代码如下：

var findCircleNum = function(isConnected) {
  var len = isConnected.length - 1
      loop = [-1, 1]
      count = 0
  function findNeighbor(I, J) {
    if (!isConnected[I][J]) return
    isConnected[I][J] = 0
    for (let i = 0; i <= len; i++) {
      for (let j = 0; j <= len; j++) {
        if (isConnected[i][j] === 1 && (i === I || j === J)) {
          findNeighbor(i, j)
        }
      }
    }
  }
  for (let i = 0; i <= len; i++) {
    for (let j = 0; j <= len; j++) {
      if (isConnected[i][j]) {
        count++
        findNeighbor(i, j)
      }
    }
  }
  return count
};
复制代码

因为其特殊的关系条件，导致在每次执行findNeighbor方法时都需要遍历一次整个二维数组，这样显然造成了性能的浪费，结果也是十分自然的，耗时和内存占用都只有最后的5%，并不推荐。

自己的答案（并查集）

在了解了具体逻辑并且看了一眼答案之后自己写出来的代码，写完发现是真的简单?：

class UnionFind {
  constructor(n) {
    this.parents = new Array(n)
    while (n--) this.parents[n] = n
  }
  findSet(x) {
    while (x !== this.parents[x]) x = this.parents[x]
    return x
  }
  unionSet(x, y) {
    var xP = this.findSet(x)
    var yP = this.findSet(y)
    if (xP !== yP) this.parents[xP] = yP
  }
  getCount() {
    return this.parents.filter((v, i) => i === v).length
  }
}

function findCircleNum(isConnected) {
  var len = isConnected.length
      uf = new UnionFind(len)
  for (let i = 0; i < len; i++) {
    for (let j = 0; j <len; j++) {
      if (isConnected[i][j]) uf.unionSet(i, j)
    }
  }
  return uf.getCount()
}
复制代码

确实很简单，但这里涉及到了上面说的第二个问题——性能问题。

笔者真是百思不得其解，这段代码看上去没啥毛病啊，可性能就是上不去，在后20%～30%之间徘徊，但这段代码是笔者参照了一个题解写出来的，整体代码十分相像，但人的题解性能就会达到50%以上，有时甚至会70%，这就有点莫名其妙了，如果有的读者看出来问题所以希望可以给笔者指正一下，感恩的❤️～

更好的方法（递归&&泛洪算法）

讲真，这种想法简直是把题目理解到了极致。

笔者在初次看这个答案的时候竟然看的一头雾水，看了好几遍，跑了几次，对照着题目才把这种方法看懂，简直是强得令人发指，几乎可以说是最强的答案了。

先看看代码，对照着解释会更好理解?：

var findCircleNum = function(isConnected) {
  var count = 0
      len = isConnected.length
      visited = new Uint8Array(len)
  function findNeighbor(i) {
    visited[i] = 1
    for (let j = len; j--;) {
      if (isConnected[i][j] && !visited[j]) findNeighbor(j)
    }
  }
  for (let j = len; j--;) {
    if (visited[j] === 0) {
      count++
      findNeighbor(j)
    }
  }
  return count
};
复制代码

这个答案是笔者自己写的，借鉴了小宇的答案后自己写出来的，和原答案有些出入，但原理是一样的，只是实现上有些小的出入，性能其实并不如原答案。

首先想理解这个答案，先要看见一个大前提——城市共有n个。

是的，也就是说省份最多也会有n个，此时的数组是酱的?：

[
	[1, 0, 0],
	[0, 1, 0],
	[0, 0, 1]
]
复制代码

结果为1的元素只有[1, 1]、[2, 2]、[3, 3]。也就是对角线上的元素。那么这里可以先将所有的城市标记为0，然后从头开始遍历城市，每遇到一个为0的城市就将其标记为1，并且在总数上加1。

之后查找与这个城市有关的城市，也就是isConnected[i][j]为1节点，拿到此时的j，如果j城市没有被标记过，那就把j城市也标记了，其值改为1，再找到与j城市相关的城市，一直进行递归。

那么最后只要返回最后的count就好了。

这种方法的好处是不用循环一个二维数组，只需要循环两次一维数组即可，也是某种意义上的降维吧。并且而外新增的内容只有一个等同于城市数量的一维数组，里面的值只有1或者0。

简单是很简单，主要是很难想到。

这里还借鉴了一些原答案的细节部分以提升性能，比方说使用Unit8Array来减少内存占用，使用for循环的--模式来进行更快的运算，原答案真的很强啊。

更好的方法（并查集）

在自己的答案并查集解法中，笔者说过有性能问答，达不到原答案的性能。

这里的原答案也是小宇写的，强得一匹，这里放一下代码，如果有读者看出了原答案比我的强在哪里希望可以在评论区回复，笔者是真的尽力了～

class UnionFind {
    constructor (n) {
        this.parents = new Uint8Array(n)
        while (n--) this.parents[n] = n
    }
    union (x, y) {
        const rootX = this.find(x), rootY = this.find(y)
        if (rootX !== rootY) this.parents[rootX] = rootY
    }
    find (x) {
        while (x !== this.parents[x]) x = this.parents[x]
        return x
    }
}

var findCircleNum = function(isConnected) {
    let i = -1, unionFind = new UnionFind(isConnected.length)
    while (++i < isConnected.length)
        for (let j = i + 1; j < isConnected[i].length; j++)
            if (isConnected[i][j]) unionFind.union(i, j)
    return unionFind.parents.filter((v, i) => v === i).length
};
复制代码