347. Top K Frequent Elements

概要

nums: Vecに対して、出現頻度が高い順にk個の要素を返す

Ruby

def top_k_frequent(nums, k)
  hash = nums.tally
  hash.max_by(k) { |_, value| value }.to_h.keys
end

tally: 各要素の出現回数をHashで返す
max_by: ブロックの評価結果が最大になる要素を返す

{foo: 0, bar: 1, baz: 2}.max_by(2) {|key, value| -value }
# => [[:foo, 0], [:bar, 1]]

Rust

use std::collections::HashMap;

use crate::Solution;

#[allow(dead_code)]
impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut map: HashMap<i32, usize> = HashMap::new();

        for &num in &nums {
            *map.entry(num).or_insert(0) += 1;
        }

        let mut sorted = vec![Vec::new(); nums.len()];

        for (&num, &count) in map.iter() {
            sorted[nums.len() - count].push(num);
        }

        sorted.into_iter().flatten().take(k as usize).collect()
    }
}

Vec<Vec> をflattenして、take(k)する
BTreeMapを使う解法も考えたが、countをkeyにすると、ダブった場合に不敵になるので使えなかった
BinaryHeapを使う解法も考えたが、BinaryHeapは最大値を取り出すだけでsortしているわけではない