suzu6RustnのHashMapを使って同じ要素をカウントして多い順に並べてみます。
Contents
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();でハッシュマップをタプルのベクトルに変換してから、タプルの２番目の要素を基準にソートします。
sort_by()は安定で最悪計算量がO(n log n)です。
ラムダ式みたいに|x, y| y.1.cmp(&x.1)とベクトルの要素を比較して整列します。
xとyを交換すると昇順になり、y.0と元キーだった要素でも比較ができる。
ハッシュマップから最小（最大）の数を取り出す
min_byとmax_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の問題
問題文
高橋君は， 個のボールを持っています． 最初， 番目のボールには，整数 が書かれています． 高橋君は，いくつかのボールに書かれている整数を書き換えて， 個のボールに書かれている整数が 種類以下になるようにしたいです． 高橋君は，少なくとも何個のボールの整数を書き換える必要があるでしょうか？
入出力や制約はAtCoderのページを見てください。
回答
クリックすると開きます。
この問題はハッシュマップでユニークな要素をそれぞれカウントして、数が小さい順に 種類分の個数を合計した数が答えになります。
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でわかる。