287.find-the-duplicate-number.md

問題

https://leetcode.com/problems/find-the-duplicate-number/

回答

初回の回答:

$[1,n]$ の範囲の数を含む配列（$length = n + 1$）の要素のうち、重複する数を求める問題。HashMap を使って、1~n までの各数字の登場回数をバリューに保存して 2 以上になっているものを特定する方法で実装した。

use std::collections::HashMap;
impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let mut nums_count = HashMap::new();
        for num in nums {
            nums_count.entry(num).and_modify(|count| *count += 1).or_insert(1);
        }
        *nums_count.iter().filter(|(k, v)| *v > &1).next().unwrap().0
    }
}

二回目の回答:

なんとか二分探索で計算量節約できないかなと思ったら Solution の一つにあった。

impl Solution {
    pub fn find_duplicate(nums: Vec<i32>) -> i32 {
        let mut l = 0;
        let mut r = nums.len() as i32;
        let mut dup = -1;
        while l < r {
            let m = l + (r - l) / 2;
            let mut count = 0;
            for num in &nums {
                if *num <= m {
                    count += 1;
                }
            }
            if count > m {
                dup = m;
                r = m;
            } else {
                l = m + 1;
            }
        }
        dup
    }
}