1337.the-k-weakest-rows-in-a-matrix.md

問題

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/

回答

初回の回答: 各行の index 付きの配列を作り、行ごとの合計値を計算してソートする

各行の兵力の合計値を計算して、弱い順にソートするという素直なアプローチ。合計値を計算するとき、各行のすべての要素を見るので兵力が少ない行ほど余計な計算量が増える。なので、要素数が数百万とかのオーダーになったときパフォーマンスに問題出てくるかもしれない。

Runtime: 5 ms, faster than 31.53% of Rust online submissions for The K Weakest Rows in a Matrix. Memory Usage: 2.3 MB, less than 15.32% of Rust online submissions for The K Weakest Rows in a Matrix.

impl Solution {
    pub fn k_weakest_rows(mat: Vec<Vec<i32>>, k: i32) -> Vec<i32> {
        let mut vec = Vec::from_iter(mat.iter().enumerate());
        vec.sort_by_cached_key(|(_, row)| row.iter().filter(|e| e.is_positive()).sum::<i32>());
        vec.iter()
            .map(|(i, _)| *i as i32)
            .take(k as usize)
            .collect()
    }
}

collect() がだめで Vec::from_iter が OK な理由がよくわからなかったけど、とりあえず前者の方はレシーバが FromIterator を implement してる型じゃないとだめっぽい。 そんなことなかった。ちゃんと type annotation してないだけだった。

以下のように index 付きの配列に mat を変換する方法はいくつかある。

• Vec::from_iter()
• collect() + type annotation
• collect::<T>()

let mut vec = Vec::from_iter(mat.iter().enumerate());
let mut vec2: Vec<(usize, &Vec<i32>)> = mat.iter().enumerate().collect();
let mut vec3 = mat.iter().enumerate().collect::<Vec<(usize, &Vec<i32>)>>();