Skip to content

Latest commit

 

History

History
133 lines (108 loc) · 4.53 KB

719.find-k-th-smallest-pair-distance.md

File metadata and controls

133 lines (108 loc) · 4.53 KB

問題

https://leetcode.com/problems/find-k-th-smallest-pair-distance/

回答

初回の回答:

この実装はパスしなかった。 組み合わせをすべて列挙して、 {距離: ペアの数} で HashMap を作る。k を ペアの回数 の少ない順に引いていき、マイナスになったときの 距離 を答えとする。 これだと $\mathcal{O(n(n - 1)/2)}$ になってしまうので、組み合わせ数が十分大きい場合に 20 秒くらいかかってしまう。

use std::collections::HashMap;
impl Solution {
    pub fn smallest_distance_pair(nums: Vec<i32>, mut k: i32) -> i32 {
    let mut distance_count: HashMap<i32, i32> = HashMap::new();
    for i in 0..nums.len() {
        for j in i + 1..nums.len() {
            let distance = i32::abs(nums[i] - nums[j]);
            distance_count
                .entry(distance)
                .and_modify(|v| *v += 1)
                .or_insert(1);
        }
    }
    let mut distance_count_vec = distance_count.iter().collect::<Vec<(&i32, &i32)>>();
    distance_count_vec.sort();
    *distance_count_vec
        .iter()
        .skip_while(|(_, v)| {
            k -= **v;
            k > 0
        })
        .next()
        .unwrap()
        .0
    }
}

二回目の回答:

公式の解法読んだけど説明がまじで意味不明過ぎて数日ほど理解できなかった。 ユーザーが投稿した解法が分かりやすかった（そして公式の説明は未だ意味不明）ので、以下にまとめてみる。 https://leetcode.com/problems/find-k-th-smallest-pair-distance/solutions/109082/approach-the-problem-using-the-trial-and-error-algorithm/

問題文で求められている、

return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

とはどういうことかと言うと以下の通りである。

0 以上の整数を要素に持つある配列 arr のうち、2 要素の組み合わせがなす距離の範囲は [0, (max(arr) - min(arr))] である。たとえば、

$$ \begin{aligned} & [1,3,1,4,5,7,5] \end{aligned} $$

という配列があった場合、

$$ \begin{aligned} & 最小の距離：(1,1)→0\\ & 最大の距離：(1,7)→6 \end{aligned} $$

となる。この 0 から 6 の距離を取る組み合わせを小さい順に並べると、

[[1, 1], [5, 5], [4, 5], [3, 4], [4, 5], [5, 7], [1, 3], [1, 3], [3, 5], [3, 5], [5, 7], [1, 4], [4, 7], [1, 4], [1, 5], [1, 5], [3, 7], [1, 5], [1, 5], [1, 7], [1, 7]]

距離ごとにグループ分けすると以下の通り。

0=>[[1, 1], [5, 5]],
1=>[[3, 4], [4, 5], [4, 5]],
2=>[[1, 3], [1, 3], [3, 5], [3, 5], [5, 7], [5, 7]],
3=>[[1, 4], [1, 4], [4, 7]],
4=>[[1, 5], [1, 5], [1, 5], [1, 5], [3, 7]],
6=>[[1, 7], [1, 7]]

たとえば、 $[1,1]$ は 1 番目の組み合わせ。１つ目の $[3,5]$ は 8 番目の組み合わせとなる。問題文の the kth smallest distance の候補は 0,1,2,3,4,6 のどれかしかないんじゃないの？と思うけど、そうではなく、k 番目の組み合わせがなす距離のことを指すらしい。find the kth smallest pair and return its distance の方がまだ分かりやすい。

とにかく、k 番目の組み合わせがなす距離を返すには、

(0 ~ m 番目までの組み合わせ総数) >= k

となるような距離 m の最小値が分かれば OK。コードに落とし込むべきことは以下の 2 つ。

  1. 取りうる距離の範囲を求める
    • 配列 nums をソートする
    • 最小値を 0、最大値を max = (nums[n-1] - nums[0])とする
  2. 0 ~ max を m の探索範囲とし、二分探索で絞っていく
    • 0 ~ m 番目までの組み合わせ総数の計算を行う
    • 組み合わせ総数 < k なら右半分に探索範囲を絞る
    • 組み合わせ総数 >= k なら左半分に探索範囲を絞る
impl Solution {
    pub fn smallest_distance_pair(mut nums: Vec<i32>, mut k: i32) -> i32 {
        nums.sort();

        let n = nums.len();
        let mut l = 0;
        let mut r = nums[n - 1] - nums[0];
        while l < r {
            let mut count = 0;
            let m = l + (r - l) / 2;
            for i in 0..n {
                let mut j = i;
                while j < n && nums[j] - nums[i] <= m {
                    j += 1;
                }
                count += (j as i32 - 1) - i as i32;
            }
            if count < k {
                l = m + 1;
            } else {
                r = m;
            }
        }
        l
    }
}