### 単純に計算していく方法
fn main() {
let mut vote = [
"山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(),
"鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(),
"鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(),
];
let n = vote.len();
let half = n / 2;
let mut winner = "".to_string();
for i in 0..n {
if vote[i] == "" {
continue;
}
let mut count = 1;
for j in i+1..n {
if vote[j] == vote[i] {
count += 1;
vote[j] = "".to_string();
if count > half {
winner = vote[i].clone();
break;
}
}
}
if winner != "".to_string() {
break;
}
}
if winner != "".to_string() {
println!("{}が過半数を取りました", winner);
} else {
println!("過半数を取った人はいません");
}
}
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/basic`
鈴木花子が過半数を取りました
### ボイアーとムーアのアルゴリズム
最初に最も多い組み合わせを調べ、それが過半数に達しているか計算する。
計算量が少なくて済む。
fn main() {
let vote = [
"山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(),
"鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(),
"鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(),
];
let n = vote.len();
let mut candidate = "".to_string();
let mut survivor = 0;
for i in 0..n {
if survivor == 0 {
candidate = vote[i].clone();
survivor = 1;
} else if candidate == vote[i] {
survivor += 1;
} else {
survivor -= 1;
}
}
let mut count = 0;
if survivor != 0 {
for i in 0..n {
if candidate == vote[i] {
count += 1;
}
}
}
if count > (n / 2) {
println!("{}が過半数を取りました。", candidate);
} else {
println!("過半数を取った人はいません。");
}
}
### ソートによるカウント
ソートして真ん中の値のカウントをする。これも美しい。
fn main() {
let mut vote = vec![
"山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(),
"鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(),
"鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(),
];
let half = vote.len() / 2;
vote.sort();
if vote.clone().into_iter().filter(|n| *n == vote[half]).count() > half {
println!("{}が過半数を取りました。", vote[half]);
} else {
println!("過半数を取った人はいません。");
}
}
### hashmapで計算する
use std::collections::HashMap;
fn main() {
let vote = [
"山田太郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(),
"鈴木花子".to_string(), "佐藤三郎".to_string(), "鈴木花子".to_string(), "佐藤三郎".to_string(),
"鈴木花子".to_string(), "鈴木花子".to_string(), "山田太郎".to_string(), "鈴木花子".to_string(),
];
let mut blackboard: HashMap<String, i32> = HashMap::new();
for v in vote.clone() {
if !blackboard.contains_key(&v) {
blackboard.insert(v.clone(),1);
} else {
blackboard.insert(v.clone(), 1 + blackboard[&v]);
}
println!("{:?}", blackboard);
}
let key_with_max_value =blackboard.iter().max_by_key(|entry | entry.1).unwrap();
if *key_with_max_value.1 as usize > (vote.len() / 2) {
println!("過半数を取得しました。{:?}", key_with_max_value);
} else {
println!("過半数を取った人はいません。");
}
}
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/basic`
{“山田太郎”: 1}
{“山田太郎”: 1, “鈴木花子”: 1}
{“山田太郎”: 1, “鈴木花子”: 1, “佐藤三郎”: 1}
{“佐藤三郎”: 1, “山田太郎”: 1, “鈴木花子”: 2}
{“佐藤三郎”: 1, “山田太郎”: 1, “鈴木花子”: 3}
{“佐藤三郎”: 2, “山田太郎”: 1, “鈴木花子”: 3}
{“佐藤三郎”: 2, “山田太郎”: 1, “鈴木花子”: 4}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 4}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 5}
{“佐藤三郎”: 3, “山田太郎”: 1, “鈴木花子”: 6}
{“佐藤三郎”: 3, “山田太郎”: 2, “鈴木花子”: 6}
{“佐藤三郎”: 3, “山田太郎”: 2, “鈴木花子”: 7}
過半数を取得しました。(“鈴木花子”, 7)
これが感覚的には一番わかりやすい。でもアルゴリズム的にはボイヤーの方が優れているんだよなー