各クエリで最も美しいアイテム

2070年。各クエリで最も美しいアイテム

難易度: 中

トピック: 配列、二分探索、並べ替え

2D 整数配列 items が与えられます。ここで、 items[i] = [price_i, Beauty_i] は、price と beauty を示します。それぞれアイテムの 。

0 インデックス付き 整数配列クエリも提供されます。各クエリ[j]について、価格がクエリ[j]の以下であるアイテムの最大の美しさを決定したいとします。そのような項目が存在しない場合、このクエリの答えは 0 になります。

クエリと同じ長さの配列の回答を返します。ここで、answer[j] は j 番目のクエリに対する回答です。

例 1:

• 入力: 項目 = [[1,2],[3,2],[2,4],[5,6],[3,5]]、クエリ = [1,2,3 、4、5、6]
• 出力: [2,4,5,5,6,6]
• 説明:
  • クエリ[0]=1 の場合、価格
  • クエリ[1]=2 の場合、考慮できる項目は [1,2] と [2,4] です。
  • その中で最大の美しさは 4 です。
  • クエリ[2]=3 およびクエリ[3]=4 の場合、考慮できる項目は [1,2]、[3,2]、[2,4]、および [3,5] です。
  • その中で最大の美しさは 5 です。
  • クエリ[4]=5 およびクエリ[5]=6 の場合、すべての項目が考慮されます。
  • したがって、彼らの答えは、すべての項目の最大の美しさ、つまり 6 です。

例 2:

• 入力: アイテム = [[1,2],[1,2],[1,3],[1,4]]、クエリ = [1]
• 出力: [4]
• 説明: すべてのアイテムの価格は 1 なので、最大の美しさ 4 を持つアイテムを選択します。
  • 複数のアイテムが同じ価格や美しさを持つ可能性があることに注意してください。

例 3:

• 入力: アイテム = [[10,1000]]、クエリ = [5]
• 出力: [0]
• 説明: 価格が 5 以下のアイテムはないため、アイテムを選択することはできません。
  • したがって、クエリの答えは 0 です。

制約:

• 1 5
• items[i].length == 2
• 1 _i、美しさ_i、クエリ[j] 9

ヒント:

1. 同じ項目を繰り返しチェックすることを避けるために、スマートな順序でクエリを処理できますか?
2. クエリに対する回答を他のクエリに使用するにはどうすればよいですか?

解決策:

並べ替えと二分探索手法を使用できます。計画は次のとおりです:

アプローチ

1. 商品を価格で並べ替えます:

   • まず、アイテムを価格順に並べ替えます。このようにして、アイテムを反復処理するときに、特定の価格までのアイテムについてこれまでに見られた最大の美しさを追跡できます。

2. クエリを元のインデックスで並べ替えます:

   • 元のインデックスとペアになったクエリの配列を作成し、この配列をクエリの値で並べ替えます。
   • 並べ替えると、クエリを価格の昇順に処理でき、より低い価格の美しさの値を繰り返し再計算する必要がなくなるため役立ちます。

3. 項目とクエリを同時に反復処理します:

   • 2 つのポインターを使用して、各クエリを処理します。
     • クエリごとに、クエリの価格以下の価格のアイテム間でポインタを移動します。
     • これらの項目を検討しながら最大の美しさを追跡し、この値を使用して現在のクエリに答えます。
     • これにより、複数のクエリに対して項目を繰り返しチェックする必要がなくなります。

4. 結果を保存して返す:

   • 処理後は、順序を維持するために元のインデックスに基づいて各クエリの最大の美しさの結果を保存します。
   • 答えの配列を返します。

このソリューションを PHP で実装してみましょう: 2070。各クエリで最も美しいアイテム

<?php
/**
 * @param Integer[][] $items
 * @param Integer[] $queries
 * @return Integer[]
 */
function maximumBeauty($items, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$items = [[1,2],[3,2],[2,4],[5,6],[3,5]];
$queries = [1,2,3,4,5,6];
print_r(maximumBeauty($items, $queries));
// Output: [2,4,5,5,6,6]
?>

説明：

• アイテムとクエリの並べ替え: これにより、冗長な計算を行わずに効率的な処理が可能になります。
• 2 ポインター手法: クエリごとに項目間を 1 回だけ移動することで、過剰な計算を回避します。
• maxBeauty を追跡: maxBeauty を段階的に更新し、各クエリがこれまでに確認された最高の美しさにアクセスできるようにします。

複雑

• 時間計算量: アイテムとクエリの並べ替えには O(n log n m log m)、および O(n m) 処理用、nは項目の長さ、m はクエリの長​​さです。
• 空間複雑度: 結果を保存するための O(m)。

このソリューションは効率的であり、問​​題の制約を満たしています。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が各クエリで最も美しいアイテムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。