349.intersection-of-two-arrays.md

問題

https://leetcode.com/problems/intersection-of-two-arrays/

回答

初回の回答:

２つの配列の共通部分を抽出する問題。まずそれぞれソートして二分探索でヒットした要素を HashSet に入れていく。HashSet はキーが重複することはないので、同じ要素が複数入ることはない。

use std::collections::HashSet;
impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        // this needs to be implemented by yourself, not calling a built-in method.
        let mut nums1_ = nums1.clone();
        let mut nums2_ = nums2.clone();
        nums1_.sort();
        nums2_.sort();

        let mut result: HashSet<i32> = HashSet::new();
        for e in &nums1_ {
            let mut l = 0;
            let mut r = nums2_.len();
            while l < r {
                let m = l + (r - l) / 2;
                match e.cmp(&nums2_[m]) {
                    std::cmp::Ordering::Equal => {
                        result.insert(*e);
                        break;
                    },
                    std::cmp::Ordering::Less => r = m,
                    std::cmp::Ordering::Greater => l = m + 1,
                }
            }
        }
        result.into_iter().collect::<Vec<i32>>()
    }
}