1632.矩阵转换后的秩.md

1632.矩阵转换后的秩

/*
 * @lc app=leetcode.cn id=1632 lang=typescript
 *
 * [1632] 矩阵转换后的秩
 */

// @lc code=start
function matrixRankTransform(matrix: number[][]): number[][] {}
// @lc code=end

解法 1: 并查集+拓扑排序

function matrixRankTransform(matrix: number[][]): number[][] {
  const m = matrix.length,
    n = matrix[0].length,
    N = m * n
  const p = new Array(N).fill(-1)
  const find = (i: number): number => (p[i] < 0 ? i : (p[i] = find(p[i])))
  const union = (i: number, j: number) => {
    let ri = find(i),
      rj = find(j)
    if (ri !== rj) {
      if (p[ri] > p[rj]) [ri, rj] = [rj, ri]
      p[ri] += p[rj]
      p[rj] = ri
    }
  }
  for (let i = 0; i < m; i++) {
    const cnt = new Map<number, number[]>()
    for (let [j, num] of matrix[i].entries()) {
      if (!cnt.has(num)) cnt.set(num, [])
      cnt.get(num)!.push(j)
    }
    for (let [, ids] of cnt) {
      if (ids.length > 1) {
        for (let j = 1; j < ids.length; j++) {
          union(i * n + ids[j], i * n + ids[j - 1])
        }
      }
    }
  }
  for (let i = 0; i < n; i++) {
    const cnt = new Map<number, number[]>()
    for (let j = 0; j < m; j++) {
      const num = matrix[j][i]
      if (!cnt.has(num)) cnt.set(num, [])
      cnt.get(num)!.push(j)
    }
    for (let [, ids] of cnt) {
      if (ids.length > 1) {
        for (let j = 1; j < ids.length; j++) {
          union(ids[j] * n + i, ids[j - 1] * n + i)
        }
      }
    }
  }

  const h = new Array(N).fill(-1),
    e: number[] = [],
    ne: number[] = [],
    d: number[] = new Array(N).fill(0)
  const add = (i: number, j: number) => (e.push(j), ne.push(h[i]), (h[i] = ne.length - 1), d[j]++)
  for (let i = 0; i < m; i++) {
    const ids = [...new Array(n).keys()].sort((a, b) => matrix[i][a] - matrix[i][b])
    for (let j = 1; j < n; j++) {
      let a = ids[j - 1],
        b = ids[j]
      if (matrix[i][a] === matrix[i][b]) continue
      add(find(i * n + a), find(i * n + b))
    }
  }
  for (let i = 0; i < n; i++) {
    const ids = [...new Array(m).keys()].sort((a, b) => matrix[a][i] - matrix[b][i])
    for (let j = 1; j < m; j++) {
      let a = ids[j - 1],
        b = ids[j]
      if (matrix[a][i] === matrix[b][i]) continue
      add(find(i + a * n), find(i + b * n))
    }
  }

  const dist = new Array(N).fill(1)
  const q: number[] = []
  for (let i = 0; i < N; i++) if (!d[i]) q.push(i)
  for (let u of q) {
    for (let i = h[u]; ~i; i = ne[i]) {
      const v = e[i]
      dist[v] = Math.max(dist[v], dist[u] + 1)
      if (--d[v] === 0) q.push(v)
    }
  }
  const res = Array.from({ length: m }, () => new Array(n))
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      res[i][j] = dist[find(i * n + j)]
    }
  }
  return res
}

Case

test.each([
  {
    input: {
      matrix: [
        [2, 3, 1],
        [9, 4, 5],
        [3, 4, 2],
      ],
    },
    output: [
      [2, 3, 1],
      [6, 4, 5],
      [3, 4, 2],
    ],
  },
  {
    input: {
      matrix: [
        [1, 2],
        [3, 4],
      ],
    },
    output: [
      [1, 2],
      [2, 3],
    ],
  },
  {
    input: {
      matrix: [
        [7, 7],
        [7, 7],
      ],
    },
    output: [
      [1, 1],
      [1, 1],
    ],
  },
  {
    input: {
      matrix: [
        [20, -21, 14],
        [-19, 4, 19],
        [22, -47, 24],
        [-19, 4, 19],
      ],
    },
    output: [
      [4, 2, 3],
      [1, 3, 4],
      [5, 1, 6],
      [1, 3, 4],
    ],
  },
])('input: matrix = $input.matrix', ({ input: { matrix }, output }) => {
  expect(matrixRankTransform(matrix)).toEqual(output)
})