每个查询最漂亮的项目-php教程-PHP中文网

首页

后端开发

php教程

每个查询最漂亮的项目

Linda Hamilton

Nov 16, 2024 am 08:18 AM

Most Beautiful Item for Each Query

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

提示：

我们能否以智能顺序处理查询以避免重复检查相同的项目？
我们如何将某个查询的答案用于其他查询？

解决方案：

我们可以使用排序和二分搜索技术。计划如下：

方法

按价格对商品排序：
- 首先，按价格对商品进行排序。这样，当我们迭代这些物品时，我们可以跟踪迄今为止所看到的任何给定价格的物品的最大美丽。
使用原始索引对查询进行排序:
- 创建一个与其原始索引配对的查询数组，然后按查询值对该数组进行排序。
- 排序很有帮助，因为我们可以按价格升序处理查询，并避免重复重新计算较低价格的美丽值。
同时迭代项目和查询:
- 使用两个指针，处理每个查询：
  - 对于每个查询，将指针移动到价格小于或等于查询价格的项目。
  - 在浏览这些项目时跟踪最大的美丽，并使用该值来回答当前的查询。
  - 这可以避免重复检查多个查询的项目。
存储并返回结果:
- 处理完成后，根据原始索引存储每个查询的最大美容结果以保持顺序。
- 返回答案数组。

让我们用 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]
?>