专栏首页算法修养LeetCode 1632. Rank Transform of a Matrix

LeetCode 1632. Rank Transform of a Matrix

题目

拖了两个月,终于这这道题目AC了。

思路是贪心,将所有的元素从小到大排序。并且维护两个数组,一个数组代表每一行的当前已经填上的最大的rank,比如nrank[0]=2 表示第0行,目前已经填到了rank=2,下一个再填就一定是>=2的数字。 同理列也是。一开始nrank[],和mrank[]都赋值为0。当我们贪心到一个元素的时候,它的rank,就是max(nrank[n], mrank[m])+1, , 然后在遍历所有元素的之前,我们需要用并查集把那些值相同并且行或者列相同的元素并起来,因为这些元素的rank值一定相同。

所以在并查集里,被合并的元素集合里的rank是集合rank最大的哪个元素的rank值。 所以实现就要把一个一个集合里的所有元素都算出它的rank,对于每一个集合都取一个最大值。那么怎么算rank,就是max(nrank[n], mrank[m])+1。当一个集合的rank确定之后, 再把集合里的所有元素的rank都填上,相应的nrank[] 和mrank[]也要改变。这个过程我们放到遍历所有从小到大排好序的数组中取实现。

最后终于过了。 还有一点,再遍历之前的并查集操作,不能用N3的操作取并,只能N2*Log(N)

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)。 ...

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

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

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

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

    狼啸风云
  • 低秩PSD矩阵的秩一测量具有较小的可行集(CS)

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

    用户8380959
  • 线性代数-单射,满射,双射,同构,同态,仿射

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

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

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

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

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

    用户7886150
  • 张量系列(tensor02)

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

    py3study
  • 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维及更高维度的数据容器。

    数据派THU
  • 利用低阶歧管正则化解决弱监督回归问题

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

    用户8436237
  • 常用算法整理

    王磊-AI基础
  • Loidreau的基于代码的密码系统的两种修改(CS IT)

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

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

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

    罗大琦
  • Predicting the Future V2更新

    Predicting the Future with Multi-scale Successor Representations

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

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

    Enjoy233
  • codeforce 266c Below the Diagonal 矩阵变换 (思维题)

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

    风骨散人Chiam
  • scipy.sparse.csr_matrix

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

    狼啸风云
  • 矩阵值函数的有理逼近算法(CS NA)

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

    非过度曝光

扫码关注云+社区

领取腾讯云代金券