每个查询最漂亮的项目
2070。每个查询最美丽的物品
难度:中等
主题:数组、二分查找、排序
给定一个 2D 整数数组 items,其中 items[i] = [pricei, beautyi] 表示 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] ?>
解释:
- 对项目和查询进行排序:这可以实现高效处理,无需冗余计算。
- 双指针技术:每个查询仅移动一次项目,避免过多的计算。
- 跟踪 maxBeauty:我们逐步更新 maxBeauty,允许每个查询访问迄今为止看到的最高美丽。
复杂
- 时间复杂度:O(n log nm log m) 用于对项目和查询进行排序,以及 O(n m) 用于处理,其中 n 是项目的长度,m 是查询的长度。
- 空间复杂度:O(m)用于存储结果。
这个解决方案是高效的并且满足问题的约束。
联系链接
如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
- 领英
- GitHub
以上是每个查询最漂亮的项目的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

在PHP中,应使用password_hash和password_verify函数实现安全的密码哈希处理,不应使用MD5或SHA1。1)password_hash生成包含盐值的哈希,增强安全性。2)password_verify验证密码,通过比较哈希值确保安全。3)MD5和SHA1易受攻击且缺乏盐值,不适合现代密码安全。

PHP和Python各有优势,选择依据项目需求。1.PHP适合web开发,尤其快速开发和维护网站。2.Python适用于数据科学、机器学习和人工智能,语法简洁,适合初学者。

PHP是一种广泛应用于服务器端的脚本语言,特别适合web开发。1.PHP可以嵌入HTML,处理HTTP请求和响应,支持多种数据库。2.PHP用于生成动态网页内容,处理表单数据,访问数据库等,具有强大的社区支持和开源资源。3.PHP是解释型语言,执行过程包括词法分析、语法分析、编译和执行。4.PHP可以与MySQL结合用于用户注册系统等高级应用。5.调试PHP时,可使用error_reporting()和var_dump()等函数。6.优化PHP代码可通过缓存机制、优化数据库查询和使用内置函数。7

PHP在电子商务、内容管理系统和API开发中广泛应用。1)电子商务:用于购物车功能和支付处理。2)内容管理系统:用于动态内容生成和用户管理。3)API开发:用于RESTfulAPI开发和API安全性。通过性能优化和最佳实践,PHP应用的效率和可维护性得以提升。

PHP类型提示提升代码质量和可读性。1)标量类型提示:自PHP7.0起,允许在函数参数中指定基本数据类型,如int、float等。2)返回类型提示:确保函数返回值类型的一致性。3)联合类型提示:自PHP8.0起,允许在函数参数或返回值中指定多个类型。4)可空类型提示:允许包含null值,处理可能返回空值的函数。

PHP仍然具有活力,其在现代编程领域中依然占据重要地位。1)PHP的简单易学和强大社区支持使其在Web开发中广泛应用;2)其灵活性和稳定性使其在处理Web表单、数据库操作和文件处理等方面表现出色;3)PHP不断进化和优化,适用于初学者和经验丰富的开发者。

PHP和Python各有优劣,选择取决于项目需求和个人偏好。1.PHP适合快速开发和维护大型Web应用。2.Python在数据科学和机器学习领域占据主导地位。

PHP适合web开发,特别是在快速开发和处理动态内容方面表现出色,但不擅长数据科学和企业级应用。与Python相比,PHP在web开发中更具优势,但在数据科学领域不如Python;与Java相比,PHP在企业级应用中表现较差,但在web开发中更灵活;与JavaScript相比,PHP在后端开发中更简洁,但在前端开发中不如JavaScript。
