。 K リストから要素をカバーする最小範囲

632。 K リストから要素をカバーする最小範囲

難易度: 難しい

トピック: 配列、ハッシュ テーブル、Greedy、スライディング ウィンドウ、ソート、ヒープ (優先キュー)

非減少順でソートされた整数のリストが k 個あります。 k 個のリストのそれぞれから少なくとも 1 つの数値を含む最小範囲を見つけます。

b - a または a

例 1:

• 入力: 数値 = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
• 出力: [20,24]
• 説明:
  • リスト 1: [4, 10, 15, 24,26]、24 は範囲 [20,24] にあります。
  • リスト 2: [0, 9, 12, 20]、20 は範囲 [20,24] にあります。
  • リスト 3: [5, 18, 22, 30]、22 は範囲 [20,24] にあります。

例 2:

• 入力: nums = [[1,2,3],[1,2,3],[1,2,3]]
• 出力: [1,1]

制約:

• nums.length == k
• 1
• 1
• -10⁵ 5
• nums[i] は 非減少 順にソートされます。

解決策:

min-heap (または優先キュー) を使用して、スライディング ウィンドウを維持しながら各リストの最小要素を追跡し、各リストから少なくとも 1 つの要素を含む最小範囲を見つけることができます。

アプローチ

1. 最小ヒープの初期化: 最小ヒープを使用して、k 個のリストのそれぞれから現在の要素を保存します。各ヒープ エントリは、値、値の元となるリストのインデックス、およびそのリスト内の要素のインデックスを含むタプルになります。
2. 最大値の追跡: 現在のウィンドウの最大値を追跡します。範囲は (ヒープからの) 最小要素と現在の最大要素との差によって決定されるため、これは重要です。
3. リストの終わりまで反復: 反復ごとに:
   • ヒープから最小限の要素を抽出します。
   • 現在の範囲 [min_value, max_value] が以前に記録された最小範囲より小さい場合は、範囲を更新します。
   • 最小要素が取得されたリスト内の次の要素に移動します。最大値を更新し、新しい要素をヒープに追加します。
4. 終了: いずれかのリストがなくなるとプロセスは終了します。

このソリューションを PHP で実装してみましょう: 632。 K リストから要素をカバーする最小範囲

<?php /**
 * @param Integer[][] $nums
 * @return Integer[]
 */
function smallestRange($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]];
$result = smallestRange($nums);
print_r($result); // Output: [20, 24]
?>

説明：

1. ヒープの初期化:
   • 初期ヒープには、各リストの最初の要素が含まれます。また、最初の要素のうち最大の要素も追跡します。
2. ヒープの処理:
   • ヒープから最小限の要素を抽出し、同じリストから次の要素を追加して範囲の拡張を試みます (可能な場合)。
   • ヒープに新しい要素を追加した後、新しい要素の方が大きい場合は maxValue を更新します。
   • maxValue と minValue の差が以前に記録された範囲よりも小さい場合は常に、最小範囲を更新します。
3. 終了:
   • すべてのリストを範囲内に含めることはもうできないため、リストの要素がなくなるとループは停止します。

複雑さの分析

• 時間計算量: O(n * log k)、n はすべてのリストの要素の合計数、k はリストの数です。複雑さは、ヒープへの要素の挿入と削除に起因します。
• 空間複雑度: ヒープに要素を格納するための O(k)。

このソリューションは、k 個の並べ替えられたリストのそれぞれから、少なくとも 1 つの数値を含む最小範囲を効率的に見つけます。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が。 K リストから要素をカバーする最小範囲の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。