719。 K 番目の最小ペア距離を求める

難易度:ハード

トピック: 配列、2 ポインター、二分探索、並べ替え

整数 a と b のペアの距離は、a と b の間の絶対差として定義されます。

整数配列 nums と整数 k を指定すると、すべてのペア nums[i] と nums[j] の間で ^k番目最小の距離を返します。ここで、0 .

例 1:

• 入力: 数値 = [1,3,1]、k = 1
• 出力: 0
• 説明: すべてのペアは次のとおりです。

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

すると、1^st の最小距離ペアは (1,1) となり、その距離は 0 になります。

例 2:

• 入力: 数値 = [1,1,1]、k = 2
• 出力: 0

例 3:

• 入力: 数値 = [1,6,1]、k = 3
• 出力: 5

制約:

• n == nums.length
• 2 4
• 0 6
• 1

ヒント：

1. 答えを二分探索します。距離

解決：

二分探索と 2 ポインタ手法を組み合わせて使用​​できます。この問題を解決するための段階的なアプローチは次のとおりです:

アプローチ：

1. 配列のソート: まず、配列の数値をソートします。並べ替えは、指定された値以下の距離を持つペアの数を効率的に計算するのに役立ちます。

2. 距離の二分検索: 二分検索を使用して、k 番目に小さい距離を見つけます。距離の検索スペースの範囲は、0 (可能な最小距離) から max(nums) - min(nums) (可能な最大距離) までです。

3. 距離 ≤ Mid のペアを数える: 二分探索の各中間値について、距離が Mid 以下のペアの数を数えます。これは、2 ポインタ アプローチを使用すると効率的に実行できます。

4. 二分探索範囲の調整: 距離がmid以下のペアの数に応じて、二分探索範囲を調整します。カウントが k 未満の場合は、下限を増やします。それ以外の場合は、上限を減らします。

このソリューションを PHP で実装しましょう: 719。 K 番目の最小ペア距離を見つける

説明：

• countPairsWithDistanceLessThanOrEqualTo: この関数は、距離が Mid 以下のペアの数をカウントします。 2 つのポインターを使用します。ここで、right は現在の要素であり、nums[right] と nums[left] の差が mid.

以下になるまで left が調整されます。

• smallestDistancePair: この関数は二分探索を使用して k 番目に小さい距離を見つけます。最小値と最大値は、距離の現在の検索範囲を定義します。中間値は、countPairsWithDistanceLessThanOrEqualTo 関数を使用してチェックされます。結果に応じて検索スペースを調整します。

このアルゴリズムは、時間計算量 O(n log(max(nums) - min(nums)) n log n) で k 番目に小さいペアの距離を効率的に見つけます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• リンクトイン
• GitHub