。 K 番目の最小ペア距離を見つける

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

難易度: 難しい

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

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

整数配列 nums と整数 k を指定すると、すべてのペアの k^番目 の最小の 距離を返します nums[i] と nums[j] (0 <) ;= 私 .

例 1:

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

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

その場合、1^番目の最小距離ペアは (1,1) で、その距離は 0 です。

例 2:

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

例 3:

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

制約:

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

ヒント:

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

解決策:

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

アプローチ：

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

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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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

• LinkedIn
• GitHub

以上が。 K 番目の最小ペア距離を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。