【Rust】HashMapで配列の同じ要素をカウントして多い順に並べる

RustnのHashMapを使って同じ要素をカウントして多い順に並べてみます。

ToC

HashMapについて

ハッシュマップはキーとそれに紐づいた値の対応関係を保持した構造です。 他の言語ではハッシュテーブルや連想配列などとも呼ばれています。

重複した要素のカウント

ベクトルにある数字をそれぞれカウントします。

use std::collections::HashMap;

fn main() {
    let vector = vec![1, 3, 4, 1, 2, 5, 2, 3, 4, 1, 3, 4, 1];
    // 要素ごとのカウント
    let mut hashmap = HashMap::new();
    for x in vector {
        let counter = hashmap.entry(x).or_insert(0);
        *counter += 1;
    }
    println!("{:?}", hashmap);
}
出力
{4: 3, 2: 2, 3: 3, 1: 4, 5: 1}

let mut hashmap = HashMap::new();でHashMapを初期化します。 後の処理で型が推測できます。

.entry(x)でキーを挿入しますが、.entry(x).or_insert(0)ではまだ存在しない場合にのみキーを挿入します。 .or_insert(0)は可変の値(<K, V>のV)の参照を返すため、*counter += 1のようにポインターで値を操作できます。

値の大きい順にソートする

ハッシュマップをカウントを降順にソートします。

// 先ほどカウントの続き

// カウント順にソート
let mut vector2: Vec<_> = hashmap.into_iter().collect();
vector2.sort_by(|x, y| y.1.cmp(&x.1));
println!("{:?}", vector2);
出力
[(1, 4), (3, 3), (4, 3), (2, 2), (5, 1)]

hashmap.into_iter().collect();でハッシュマップをタプルのベクトルに変換してから、タプルの2番目の要素を基準にソートします。 sort_by()は安定で最悪計算量がO(n log n)です。 ラムダ式みたいに|x, y| y.1.cmp(&x.1)とベクトルの要素を比較して整列します。 xとyを交換すると昇順になり、y.0と元キーだった要素でも比較ができる。

ハッシュマップから最小(最大)の数を取り出す

min_bymax_byで最小と最大の要素をとりだせます。

// 最小を取得
let min = hashmap.iter()
  .min_by(|a, b| a.1.cmp(&b.1))
  .unwrap();
// (5, 1)


// 最大を取得
let max = hashmap.iter()
  .max_by(|a, b| a.1.cmp(&b.1))
  .unwrap();
// (1, 4)

ハッシュマップを使ったAtCoderの問題

問題文

高橋君は,NN 個のボールを持っています. 最初,ii 番目のボールには,整数 AiA_i が書かれています. 高橋君は,いくつかのボールに書かれている整数を書き換えて,NN 個のボールに書かれている整数が KK 種類以下になるようにしたいです. 高橋君は,少なくとも何個のボールの整数を書き換える必要があるでしょうか?

ABC081 - C Not so Diverse

入出力や制約はAtCoderのページを見てください。

回答

クリックすると開きます。

回答と考え

この問題はハッシュマップでユニークな要素をそれぞれカウントして、数が小さい順に KUnique(Ai)K - Unique(Ai) 種類分の個数を合計した数が答えになります。

use std::collections::HashMap;
use std::collections::HashSet;

fn main() {
    proconio::input! {
        n: i32,
        k: i32,
        a: [i32; n]
    }
    // ユニークな数
    let uniq: HashSet<i32> = a.clone().into_iter().collect();
    let len = uniq.len() as i32 - k;
    if len <= 0 {
        println!("0");
        return;
    }
    // 要素ごとのカウント
    let mut map = HashMap::new();
    for x in a {
        let counter = map.entry(x).or_insert(0);
        *counter += 1;
    }
    // カウント順にソート
    let mut v: Vec<_> = map.into_iter().collect();
    v.sort_by(|x, y| x.1.cmp(&y.1));
    v.reverse();
    // println!("{:?}", v);
    let mut answer = 0;

    // 数が小さいものからk以下まで足し算
    for _ in 0..len {
        answer += v.pop().unwrap().1;
    }
    println!("{}", answer);
}

ユニークなボールの数はHashSetでわかる。

 関連記事

 新着 or 更新記事