This is the c++ solution to this programming problem (LeetCode 1329. Sort the Matrix Diagonally).
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int m = mat.size();
int n = mat[0].size();
map<int, priority_queue<int>> mq;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
mq[i - j].push(-mat[i][j]);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
priority_queue<int>& q = mq[i - j];
mat[i][j] = -q.top();
q.pop();
}
}
return mat;
}
When I was converting this C++ code to Rust, I ran into a problem that I couldn't figure out.
use std::collections::HashMap;
use priority_queue::PriorityQueue;
fn diagonal_sort(mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut mat = mat.clone();
let m = mat.len();
let n = mat[0].len();
let mut mq: HashMap<i32, PriorityQueue<i32, i32>> = HashMap::new();
println!("m {}, n {}", m, n);
for i in 0..mat.len() {
for j in 0..mat[0].len() {
mq.entry(i as i32 - j as i32).or_insert(PriorityQueue::new()).push(mat[i][j], mat[i][j]);
}
}
for i in 0..mat.len() {
for j in 0..mat[0].len() {
// Ideally, how do I pop here and use the results directly?
let res = mq[&(i as i32 - j as i32)].peek();
mat[i][j] = *(match res {
Some((x, _y)) => x,
None => &(-1),
});
// Or how do I pop from the priority queue here without peeking?
// mq[&(i as i32 - j as i32)].pop();
}
}
mat
}
Pop from the priority queue here without peeking:
let v = d.get_mut(&key).unwrap();
mat[i][j] = v.pop().unwrap().0;
Result (output):
input:
9 8 7
6 5 4
3 2 1
output:
1 4 7
2 5 8
3 6 9
And you may use std::cmp::Reverse for reverse ordering:
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashMap;
pub fn diagonal_sort(mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut mat = mat.clone();
let mut mh: HashMap<i32, BinaryHeap<_>> = HashMap::new();
for i in 0..mat.len() {
for j in 0..mat[0].len() {
let key = i as i32 - j as i32;
mh.entry(key)
.or_insert(BinaryHeap::new())
.push(Reverse(mat[i][j]));
}
}
for i in 0..mat.len() {
for j in 0..mat[0].len() {
let key = i as i32 - j as i32;
let q = mh.get_mut(&key).unwrap();
match q.pop().unwrap() {
Reverse(v) => mat[i][j] = v,
}
}
}
mat
}
fn main() {
let m = vec![vec![9, 8, 7], vec![6, 5, 4], vec![3, 2, 1]];
show("input:", &m);
let s = diagonal_sort(m);
show("output:", &s);
}
fn show(s: &str, mat: &Vec<Vec<i32>>) {
println!("{}", s);
let m = mat.len();
let n = mat[0].len();
for i in 0..m {
for j in 0..n {
print!("{} ", mat[i][j]);
}
println!();
}
}
Result (output):
input:
9 6 3
8 5 2
7 4 1
output:
1 2 3
4 5 6
7 8 9
Try this (for diagonally distinct elements):
use priority_queue::PriorityQueue;
use std::collections::HashMap;
fn diagonal_sort(mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut d: HashMap<i32, PriorityQueue<i32, i32>> = HashMap::new();
let mut mat = mat.clone();
let m = mat.len();
let n = mat[0].len();
for i in 0..m {
for j in 0..n {
let key = i as i32 - j as i32;
let v = -mat[i][j];
d.entry(key).or_insert(PriorityQueue::new()).push(v, v);
}
}
for i in 0..m {
for j in 0..n {
let key = i as i32 - j as i32;
let v = d.get_mut(&key).unwrap();
mat[i][j] = -v.pop().unwrap().0;
}
}
mat
}
fn main() {
let m = vec![vec![9, 6, 3], vec![8, 5, 2], vec![7, 4, 1]];
show("input:", &m);
let s = diagonal_sort(m);
show("output:", &s);
}
fn show(s: &str, mat: &Vec<Vec<i32>>) {
println!("{}", s);
let m = mat.len();
let n = mat[0].len();
for i in 0..m {
for j in 0..n {
print!("{} ", mat[i][j]);
}
println!();
}
}
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다