排序 + 模拟,LeetCode 1329. 将矩阵按对角线排序

devtools/2024/9/24 17:14:07/

一、题目

1、题目描述

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线,沿右下方向一直到矩阵末尾的元素。例如,矩阵 mat 有 6 行 3 列,从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]mat[3][1] 和 mat[4][2] 。

给你一个 m * n 的整数矩阵 mat ,请你将同一条 矩阵对角线 上的元素按升序排序后,返回排好序的矩阵。

2、接口描述

python3
class Solution:def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
cpp
class Solution {
public:vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {}
};

3、原题链接

1329. 将矩阵按对角线排序


二、解题报告

1、思路分析

遍历每一条对角线,放入临时数组排序完再放回去即可

2、复杂度

时间复杂度: O(mn log min(m, n)) 空间复杂度:O(min(m, n))

3、代码详解

python3
class Solution:def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:m, n = len(mat), len(mat[0])for i in range(m - 1, -1, -1):x, y = i, 0a = []while x < m and y < n:a.append(mat[x][y])x += 1y += 1x, y = i, 0for t in sorted(a):mat[x][y] = tx += 1y += 1for i in range(1, n):x, y = 0, ia = []while x < m and y < n:a.append(mat[x][y])x += 1y += 1x, y = 0, ifor t in sorted(a):mat[x][y] = tx += 1y += 1return mat
cpp
class Solution {
public:vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {int m = mat.size(), n = mat[0].size();for(int i = m - 1; ~i; i --){vector<int> a;for(int x = i, y = 0; x < m && y < n; x ++, y ++ )a.emplace_back(mat[x][y]);sort(a.begin(), a.end());for(int x = i, y = 0, t = 0; x < m && y < n; x ++, y ++, t ++)mat[x][y] = a[t];}for(int i = 1; i < n; i ++){vector<int> a;for(int x = 0, y = i; x < m && y < n; x ++, y ++ )a.emplace_back(mat[x][y]);sort(a.begin(), a.end());for(int x = 0, y = i, t = 0; x < m && y < n; x ++, y ++, t ++)mat[x][y] = a[t];}return mat;}
};


http://www.ppmy.cn/devtools/24968.html

相关文章

elementPlus treeselect相关问题

<el-tree-selectplaceholder"请选择业务代码":props"{ label: transactionName, value: transactionCode }"v-model"item.transactionCode"node-key"id":data"transactionList":default-expanded-keys"[item.transa…

前端可以掌握的nginx相关操作

一、前言&#xff1a; 在日常开发中&#xff0c;前端工程师可以把打好的前端包直接放到测试服务器上&#xff0c;自己再验证功能是否改好&#xff0c;这样可以提高开发效率&#xff0c;写篇笔记记录一下我个人用到的命令 二、使用的工具 用MobaXterm完成相关操作&#xff0c…

Rust Vec<T> 集合使用教程

Rust Vec 集合使用教程 文章目录 Rust Vec<T> 集合使用教程1. 创建和初始化 Vec<T>代码示例运行结果 2. 访问和修改 Vec<T> 中的元素代码示例运行结果 3. 添加和删除 Vec<T> 中的元素代码示例运行结果 4. 遍历 Vec<T>代码示例运行结果 5. 使用 V…

SRTP + RTCP + SCTP

SRTP&#xff08;Secure Real-time Transport Protocol&#xff09; 主要功能&#xff1a;SRTP 是 RTP 的一个扩展&#xff0c;提供额外的安全特性&#xff0c;如加密、完整性校验和认证。它旨在保护实时传输的音频和视频流不被窃听或篡改。加密传输&#xff1a;SRTP 使用强加密…

源码篇--Nacos服务--中章(8):Nacos服务端感知客户端实例变更-3

文章目录 前言一、客户端实例变更&#xff1a;二、实例变更感知&#xff1a;2.1 实例注册信息通知&#xff1a;2.1.1 接收DistroDataRequest 请求&#xff1a;2.1.2 onReceive 处理请求&#xff1a;2.1.3 processData 处理请求&#xff1a;2.1.4 handlerClientSyncData 处理数据…

《python编程从入门到实践》day16

昨日知识点回顾 从模块中导入类/模块 今日知识点学习 第十章 文件和异常 10.1 从文件中读取数据 10.1.1 读取整个文件 txt文件与程序文件在同一级目录 with open(pi_digits.txt) as file_object:contents file_object.read() print(contents)# 运行结果&#xff1a; # 3.1…

数据脱敏及数据库安全风险

数据脱敏是什么 数据脱敏&#xff0c;指对某些敏感信息通过脱敏规则进行数据的变形&#xff0c;实现敏感隐私数据的可靠保护。这样就可以在开发、测试和其它非生产环境以及外包环境中安全地使用脱敏后的真实数据集。 在涉及客户安全数据或者一些商业的敏感数据的情况下&#…

格雷希尔E10系列大电流测试连接器,在新能源汽车大电流接插件的电气测试方案

在新能源汽车的电驱动、电池包等设备的电测试处理中&#xff0c;格雷希尔E10系列电测试连接器具有显著的优势。E10系列的核心设计——插孔/插针&#xff0c;可以达到实验室10万次的插拔寿命&#xff0c;相比传统公母电接头500次左右的连接寿命&#xff0c;E10系列无疑大大减少测…