[LeetCode][Hard] Ранговое преобразование матричного ранга после матричного преобразования | Java

вопрос

Rank Transform of a Matrix Hard

Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].

The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:

• The rank is an integer starting from 1.

• If two elements p and q are in the same row or column, then:

  • If p < q then rank(p) < rank(q)
  • If p == q then rank(p) == rank(q)
  • If p > q then rank(p) > rank(q)

• The rank should be as small as possible.

It is guaranteed that answer is unique under the given rules.

 

Example 1:

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.

Example 2:

Input: matrix = [[7,7],[7,7]]
Output: [[1,1],[1,1]]

Example 3:

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]]

Example 4:

Input: matrix = [[7,3,6],[1,4,5],[9,8,2]]
Output: [[5,1,4],[1,2,3],[6,3,1]]

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 500
• -109 <= matrix[row][col] <= 109

Hint 1

Sort the cells by value and process them in increasing order.

Hint 2

The rank of a cell is the maximum rank in its row and column plus one.

Hint 3

Handle the equal cells by treating them as components using a union-find data structure.

Идеи решения проблем

Этот вопрос кажется простым, но на самом деле он очень сложный. Что ищется, так это ранг матрицы, который обычно известен как ранжирование.трудностьв:

1. Ранги в рангах будут влиять друг на друга, напримерpранг в ряду3, а в колонке4, то окончательный рейтинг4
2. Узлы с одинаковым значением в одном столбце должны иметь одинаковый рейтинг, что повлияет на ранжирование нескольких строк и нескольких столбцов, например[3,2], [3,4], [5,4]Значения узлов совпадают, тогда первый3ОК, нет.5ОК, нет.2колонка,4столбецРейтинг будет влиять друг на друга

К счастью, LeetCode приготовил для нас три хитрых трюка, давайте рассмотрим их как ключ к решению проблемы.

Hint 1

Sort the cells by value and process them in increasing order.

Первый совет — давайте объединим все узлыСортировать, затем следуйтес детствапоследовательная обработка. Преимущество этого заключается в том, что на меньшие узлы, обработанные ранее, больше не влияют более поздние узлы. Мы можем преобразовать каждый узел в структуру данных или массив, напримерint[3],в[0]представляет значение узла,[1]означает ряд,[2]Представляет столбец. Вся матрица может быть преобразована вint[][] arr = new int[m*n][3]. OkСортировать, затем следуйтес детствапоследовательная обработка.

Hint 2

The rank of a cell is the maximum rank in its row and column plus one.

Второй совет — позволить нам записывать максимальный рейтинг текущей строки и столбца при обработке в указанном выше порядке, а рейтинг соответствующего узла больше максимального рейтинга текущей строки и столбца.+1. Конечно, после завершения обработки ранжирование узла также должно использоваться как максимальное ранжирование соответствующих рангов. мы можем использоватьint[] currRankRowsа такжеint[] currRankColsдля записи максимального рейтинга всех текущих рангов.

Hint 3

Handle the equal cells by treating them as components using a union-find data structure.

Третий совет: позвольте нам использоватьи проверитьиметь дело с узлами равного значения. Поиск по объединению считается одной из самых кратких и элегантных структур данных, в основном используемых для решения некоторых задач.группировка элементовПроблема. Он управляет сериейнепересекающиеся множестваи поддерживает две операции:

• сливаться(Союз): объединяет два непересекающихся набора в один набор.
• Запрос(Найти): Запрос, находятся ли два элемента в одном наборе.

Этот комплект можно использовать для решения трудности этой проблемы, о которой мы упоминали ранее, то есть, как с ней бороться.Взаимодействие между рангами. Мы можем рассматривать строки и столбцы как элементы одного типа, разделить строки и столбцы, затронутые узлами одного и того же значения, в одну и ту же группу, а затем унифицировать ранжирование в группе (поскольку узлы одного и того же значения в одном и том же столбце ,Ранг должен быть одинаковым). Итак, мы определяем$f$является объединением, используяxПредставляет строку или столбец. для элемента матрицыmatrix[i][j],когдаxУказывает время линии,x = i;когдаxПри представлении столбцаx = m + j,вmэто общее количество строк в матрице. Согласно определению объединения поиска,$f(x)$направлениеxродительский узел, а для корневого узла$f(x)=x$.

справочный ответ

class Solution {

    int[] f; // union-find set

    public int[][] matrixRankTransform(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] ret = new int[m][n];

        int[] currRankRows = new int[m];
        int[] currRankCols = new int[n];

        // initial union-find data structure, contains all the rows & cols, the length is m + n
        int[] initF = new int[m + n];
        for (int i = 0; i < m + n; i++) {
            initF[i] = i;
        }

        // put all cells into an array then sort
        int[][] arr = new int[m*n][3];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i*n+j][0] = matrix[i][j];
                arr[i*n+j][1] = i;
                arr[i*n+j][2] = j;
            }
        }

        Arrays.sort(arr, Comparator.comparingInt(o->o[0]));

        int i = 0;
        // loop the array with all matrix cells
        while(i < arr.length) {
            int target = arr[i][0];
            List<int[]> equals = new ArrayList<>();

            // get cells that has same value
            while (i < arr.length && target == arr[i][0]) {
                equals.add(arr[i]);
                i++;
            }

            // Union-find data structure
            f = initF.clone();

            // union set for f(x)
            for (int[] cell : equals) {
                union(cell[1], cell[2] + m);
            }

            // if equal numbers in same row/col, then group into map by f(x), as these need to have same rank
            Map<Integer, List<int[]>> map = new HashMap<>();
            for (int[] cell : equals) {
                int k = find(cell[1]);
                if (!map.containsKey(k)) {
                    map.put(k, new ArrayList<>());
                }
                map.get(k).add(cell);
            }

            // handle group by group
            for (List<int[]> group : map.values()) {
                // find max rank in group
                int maxRank = 0;
                for (int[] cell : group) {
                    int row = cell[1];
                    int col = cell[2];
                    maxRank = Math.max(maxRank, Math.max(currRankRows[row], currRankCols[col]) + 1);
                }
                // update max rank to current rank of rows & cols
                for (int[] cell : group) {
                    int row = cell[1];
                    int col = cell[2];
                    ret[row][col] = maxRank;
                    currRankRows[row] = Math.max(currRankRows[row], maxRank);
                    currRankCols[col] = Math.max(currRankCols[col], maxRank);
                }
            }
        }

        return ret;
    }

    int find (int x) {
        if (f[x] != x) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    void union(int x, int y) {
        int fm = find(x);
        int fn = find(y);
        f[fm] = fn;
    }


}

Внешняя граница

Перейдите в колонку автора LeetCode, чтобы узнать, есть ли другие интересные вопросы!

Наггетс.Талант/колонка/6997…

Информационная ссылка

оригинальное названиеLee TCO's.com/problems/people...

и проверитьЭто.Wikipedia.org/wiki/%E5%B9…