每個查詢最漂亮的項目

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，可以考慮的項是[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. 同時迭代項目與查詢:

   • 使用兩個指針，處理每個查詢：
     • 對於每個查詢，將指標移到價格小於或等於查詢價格的項目。
     • 在瀏覽這些項目時追蹤最大的美麗，並使用該值來回答當前的查詢。
     • 這可以避免重複檢查多個查詢的項目。

4. 儲存並回傳結果:

   • 處理完成後，根據原始索引儲存每個查詢的最大美容結果以保持順序。
   • 返回答案數組。

讓我們用 PHP 實作這個解決方案：2070。每個查詢最美麗的物品

解釋：

• 對項目和查詢進行排序：這可以實現高效處理，無需冗餘計算。
• 雙指標技術：每個查詢僅移動一次項目，避免過多的計算。
• 追蹤 maxBeauty：我們逐步更新 maxBeauty，允許每個查詢訪問迄今為止看到的最高美麗。

複雜

• 時間複雜度：O(n log nm log m) 用於項目和查詢排序，以及O(n m) 用於處理，其中n 是項目的長度，m 是查詢的長度。
• 空間複雜度：O(m)用於儲存結果。

這個解決方案是高效的並且滿足問題的限制。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是每個查詢最漂亮的項目的詳細內容。更多資訊請關注PHP中文網其他相關文章！