ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

### 単純に計算していく方法

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)

これが感覚的には一番わかりやすい。でもアルゴリズム的にはボイヤーの方が優れているんだよなー