首页 后端开发 php教程 每个查询最漂亮的项目

每个查询最漂亮的项目

Nov 16, 2024 am 08:18 AM

Most Beautiful Item for Each Query

2070。每个查询最美丽的物品

难度:中等

主题:数组、二分查找、排序

给定一个 2D 整数数组 items,其中 items[i] = [pricei, beautyi] 表示 pricebeauty 分别表示一个项目。

您还会获得一个 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。每个查询最美丽的物品

<?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中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

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

热门文章

<🎜>:泡泡胶模拟器无穷大 - 如何获取和使用皇家钥匙
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系统,解释
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆树的耳语 - 如何解锁抓钩
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

热门话题

Java教程
1666
14
CakePHP 教程
1425
52
Laravel 教程
1325
25
PHP教程
1273
29
C# 教程
1252
24
说明PHP中的安全密码散列(例如,password_hash,password_verify)。为什么不使用MD5或SHA1? 说明PHP中的安全密码散列(例如,password_hash,password_verify)。为什么不使用MD5或SHA1? Apr 17, 2025 am 12:06 AM

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

PHP和Python:比较两种流行的编程语言 PHP和Python:比较两种流行的编程语言 Apr 14, 2025 am 12:13 AM

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

PHP:网络开发的关键语言 PHP:网络开发的关键语言 Apr 13, 2025 am 12:08 AM

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

PHP行动:现实世界中的示例和应用程序 PHP行动:现实世界中的示例和应用程序 Apr 14, 2025 am 12:19 AM

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

PHP类型提示如何起作用,包括标量类型,返回类型,联合类型和无效类型? PHP类型提示如何起作用,包括标量类型,返回类型,联合类型和无效类型? Apr 17, 2025 am 12:25 AM

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

PHP的持久相关性:它还活着吗? PHP的持久相关性:它还活着吗? Apr 14, 2025 am 12:12 AM

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

PHP和Python:代码示例和比较 PHP和Python:代码示例和比较 Apr 15, 2025 am 12:07 AM

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

PHP与其他语言:比较 PHP与其他语言:比较 Apr 13, 2025 am 12:19 AM

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

See all articles