# LeetCode 1632. Rank Transform of a Matrix

```struct Node
{
int value;
int x;
int y;
Node() {}
Node(int x, int y, int value)
{
this->x = x;
this->y = y;
this->value = value;
}
}a[250005],b[505];

int compare(Node a, Node b)
{
return a.value < b.value;
}
class Solution {
public:
int n, m;
int rrank[505][505];
int nrank[505][505];
int mrank[505][505];
int f[250005];
int v[250005];
int rn[505];
int rm[505];
int tag[505][505];

int find(int x)
{
if (f[x] != x)
f[x] = find(f[x]);
return f[x];
}
void join(int x, int y)
{
int fx = find(x);
int fy = find(y);
f[fy] = fx;
}

vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
n = matrix.size();
m = matrix[0].size();

int pos = 0;
int pos2 = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
a[pos++] = Node(i, j, matrix[i][j]);
}
}

sort(a, a + pos, compare);

for (int i = 0; i < pos; i++)
{
tag[a[i].x][a[i].y] = i;
f[i] = i;
}

for (int i = 0; i < n; i++)
{
pos2 = 0;
for (int j = 0; j < m; j++)
{
b[pos2++] = Node(i, j, matrix[i][j]);
}

sort(b, b + pos2, compare);

for (int j = 1; j < pos2; j++)
{
if (b[j].value != b[j - 1].value)
{
continue;
}
else
{
int fx = find(tag[i][b[j - 1].y]);
int fy = find(tag[i][b[j].y]);

f[fx] = fy;
}
}
}

for (int i = 0; i < m; i++)
{
pos2 = 0;
for (int j = 0; j < n; j++)
{
b[pos2++] = Node(j, i, matrix[j][i]);
}

sort(b, b + pos2, compare);

for (int j = 1; j < pos2; j++)
{
if (b[j].value != b[j - 1].value)
{
continue;
}
else
{
int fx = find(tag[b[j-1].x][i]);
int fy = find(tag[b[j].x][i]);

f[fx] = fy;
}
}
}

int start = 0;
for (int i = 0; i < pos; i++)
{

int ran = max(rn[a[i].x], rm[a[i].y]) +1;
int ff = find(i);
if (v[ff] < ran)
{
v[ff] = ran;
}

if (i== pos-1 ||a[i + 1].value != a[i].value)
{
for (int j = start; j <= i; j++)
{
int xx = v[find(j)];
rrank[a[j].x][a[j].y] = xx;
rn[a[j].x] = xx;
rm[a[j].y] = xx;
}

start = i + 1;
}
}

vector<vector<int>> ans;
for (int i = 0; i < n; i++)
{
vector<int> res;
for (int j = 0; j < m; j++)
{
res.push_back(rrank[i][j]);
}
ans.push_back(res);
}

return ans;

}
};```

0 条评论

• ### spark杂记：movie recommendation using ALS

版权声明：本文为博主原创文章，未经博主允许不得转载。有问题可以加微信：lp9628(注明CSDN)。 ...

• ### 低观测分配系统中状态估计的联合矩阵完成和压缩感知（CS）

配电网有限的测量可用性对状态估计和态势感知提出了挑战。本文结合了最近提出的两种基于稀疏性的状态估计方法（矩阵完成和压缩感测）的优势，以应对不可观测性的挑战。所提...

• ### torch(七)、Math operations(2)

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 低秩PSD矩阵的秩一测量具有较小的可行集（CS）

我们研究约束集在确定低秩正半定（PSD）矩阵传感问题的解决方案中的作用。我们考虑的设置涉及等级1感测矩阵：特别是，给定近似低等级PSD矩阵的等级1投影集，我们表...

• ### 线性代数-单射,满射,双射,同构,同态,仿射

但 f(x) = 2x 从自然数集\(N\)到\(N\)不是满射，因为没有一个自然数\(N\)可以被这个函数映射到 3。

• ### 【论文推荐】最新5篇网络节点表示（Network Embedding）相关论文—高阶网络、矩阵分解、多视角、虚拟网络、云计算

【导读】专知内容组整理了最近五篇网络节点表示（Network Embedding）相关文章，为大家进行介绍，欢迎查看! 1. HONE: Higher-Orde...

• ### python pca主成分_主成分分析pca本质和python案例研究

Data is the fuel of big data era, and we can get insightful information from dat...

• ### 张量系列（tensor02）

The matrix trace is equivalent to the contraction of a rank-2 array

• ### Using ridge regression to overcome linear regression's shortfalls

In this recipe, we'll learn about ridge regression. It is different from vanilla...

• ### 一文解读Tensor到底是个啥玩意儿？（附代码）

本文介绍了各种数值型数据的容器（标量、向量、矩阵、张量）之间的关系，在实践中，张量特指3维及更高维度的数据容器。

• ### 利用低阶歧管正则化解决弱监督回归问题

我们解决的是一个弱监督回归问题。在 "弱 "下，我们理解为对于一些训练点的标签是已知的，对于一些训练点的标签是未知的，而对于其他训练点的标签则由于随机噪声的存在...

• ### Loidreau的基于代码的密码系统的两种修改（CS IT）

本文介绍了对Loidreau的基于代码的密码系统的两种修改。Loidreau密码系统是在McEliece环境下使用Gabidulin码构建的基于秩度量的密码系统...

• ### 一种用于可分离的非负矩阵分解的量子启发经典算法

作者：Zhihuai Chen,Yinan Li,Xiaoming Sun,Pei Yuan,Jialin Zhang

• ### Predicting the Future V2更新

Predicting the Future with Multi-scale Successor Representations

• ### C#版 - Leetcode 633. 平方数之和 - 题解

在线提交: https://leetcode.com/problems/sum-of-square-numbers/

• ### codeforce 266c Below the Diagonal 矩阵变换 （思维题）

You are given a square matrix consisting of n rows and n columns. We assume that...

• ### scipy.sparse.csr_matrix

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 矩阵值函数的有理逼近算法（CS NA）

本文讨论了矩阵值函数有理逼近的几种算法，包括插值AAA法、基于近似最小二乘拟合的RKFIT法、向量拟合的RKFIT法和基于块Loewner矩阵低秩逼近的RKFI...