面试题16.19.水域大小.md

面试题 16.19.水域大小

/*
 * @lc app=leetcode.cn id=面试题 16.19 lang=typescript
 *
 * [面试题 16.19] 水域大小
 */
// @lc code=start
function pondSizes(land: number[][]): number[] {}
// @lc code=end

解法 1: 并查集

function pondSizes(land: number[][]): number[] {
  const m = land.length,
    n = land[0].length
  const p = new Array(m * n).fill(-1)
  const find = (i: number) => {
    if (p[i] < 0) return i
    p[i] = find(p[i])
    return p[i]
  }
  const union = (i: number, j: number) => {
    let ri = find(i),
      rj = find(j)
    if (ri === rj) return
    if (p[ri] > p[rj]) [ri, rj] = [rj, ri]
    p[ri] += p[rj]
    p[rj] = ri
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (land[i][j] !== 0) continue
      const a = i * n + j
      for (let k = -1; k < 2; k++) {
        for (let l = -1; l < 2; l++) {
          const ni = k + i,
            nj = l + j
          if (ni < 0 || ni >= m || nj < 0 || nj >= n || (!k && !l) || land[ni][nj] !== 0) continue
          const b = ni * n + nj
          union(a, b)
        }
      }
    }
  }

  const res: number[] = []
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const a = i * n + j

      if (land[i][j] === 0 && p[a] < 0) res.push(-p[a])
    }
  }
  return res.sort((a, b) => a - b)
}

Case

test.each([
  {
    input: {
      land: [
        [0, 2, 1, 0],
        [0, 1, 0, 1],
        [1, 1, 0, 1],
        [0, 1, 0, 1],
      ],
    },
    output: [1, 2, 4],
  },
])('input: land = $input.land', ({ input: { land }, output }) => {
  expect(pondSizes(land)).toEqual(output)
})