程序员经验分享-hwhale

是否有可能在 O(n) 时间内找到给定数组中的所有三元组？

2023-12-01

给定一个数字数组，找到满足给定条件的所有三元组。

健康）状况：a[i] < a[j] < a[k] where I < j < k.

有可能在O(n)时间内解决这个问题吗？

这不是家庭作业！


输出的大小（最坏情况）是复杂性的下限。

由于可能存在 O(n^3) 个这样的三元组，因此复杂度不可能是 O(n)。

例如，如果数组从最低到最高排序，则您将有 n 选择 3 个这样的三元组，其顺序为 n^3。

如果问题涉及寻找number三胞胎，这是我看到的最有效的解决方案：

https://cs.stackexchange.com/questions/7409/count-unique-increasing-subsequences-of-length-3-in-on-log-n

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Arrays

Algorithm

find

Triplet

是否有可能在 O(n) 时间内找到给定数组中的所有三元组？ 的相关文章

  • 检查 PHP 数组中特定值的出现次数 [重复]

    这个问题在这里已经有答案了 我有一个名为 uid 的数组 如何检查值 12 在我的 uid 数组中出现了多少次 几种方法 cnt count array filter uid function a return a 12 or tmp ar

  • 数组向量无法编译[重复]

    这个问题在这里已经有答案了 这个简单的程序 include

  • 递归 - 与 Java 中不重复的数组相结合

    所以我知道如何获取组合的大小 数组大小 在我的例子中 除以所需数组子集大小的阶乘 我遇到的问题是获取组合 到目前为止 我已经阅读了 stackoverflow 上的大部分问题 但一无所获 我认为我发现的问题是我想将创建的组合子集中的元素添加

  • 从 VBA 函数返回数组的正确方法

    我的学校使用 Excel 2016 前 array 时代 因此我使用 VBA 来定义一些我需要的缺失函数 我尝试在 VBA 中实现的一个函数是SEQUENCE 替换 就像这样 Function MYSEQ n As Integer m As

  • 返回深度嵌套数组中对象的索引的函数

    我可能需要编写一个函数 仅输出数组内对象的索引 显然 使用 inArray 在下面的示例中返回这个索引就可以了 array one two three inArray one array 0 对于更复杂的数组 如何找到嵌套对象的索引 arr

  • 用于计算井字游戏独特状态的高效算法

    我正在尝试构建一个井字游戏来演示和实验机器学习算法 并且我发现了一个有趣的问题 例如 井字棋板可以是mirrored 但出于机器学习的目的 这两种状态是等效的 x o o x o o x x o o 同样地旋转 x o x o o o x

  • 如何快速计算集合的所有交集的包含顺序

    这是后续如何在python中快速获取集合的所有交集 https stackoverflow com questions 37622153 我有一个整数有限集合 Ai 的有限集合 A A1 Ak 我想计算Python下列 A 子集的所有交集

  • 在 bash 中传递多个数组作为参数

    我已经成功地能够调用单个数组作为参数 但在传递多个数组时遇到问题 这是我到目前为止所拥有的 calling function array1 1 2 3 4 array2 a b c d array3 called function arra

  • 理解 Haskell 中的矩阵转置函数

    这个矩阵转置函数有效 但我试图理解它的逐步执行 但我不明白 transpose a gt a transpose transpose x map head x transpose map tail x with transpose 1 2

  • 如何在 PHP 中随机组合两个数组

    如何将两个数组组合成一个数组 我请求的方式是第三个组合数组应包含一个数组中的一个值和另一个数组中的下一个值 依此类推 或者 它可以是随机的 前任 arr1 1 2 3 4 5 arr2 10 20 30 40 50 和组合数组 arr3 1

  • 这个简单的洗牌算法是否会返回一副随机洗牌的扑克牌？ [关闭]

    Closed 这个问题是无关 help closed questions 目前不接受答案 您有一个包含 52 张卡片的列表 其中列表中卡片的位置不会移动 您有第二个卡位置列表 首先 位置列表与第一个列表相同 迭代第一个列表 对于第一个列表中

  • 在 PHP 中将数组转换为字符串并将其恢复为数组

    我正在使用 Serialize 函数将数组存储在我的 MYSQL 数据库中 然后我在其他页面中取消序列化他 数组结构如下所示 Array 0 gt Array names gt somename1 rating gt 10 1 gt Arr

  • 字典条目被覆盖？ [复制]

    这个问题在这里已经有答案了 我发现一些输入没有存储在 Python 3 的字典中 运行这段代码 N int input How many lines of subsequent input graph for n in range N st

  • 在 Java 中从复杂的 HTML 表格中提取数据到二维数组

    如何转换 HTML 表格带有 colspan 和 rowspanJava中的二维数组 矩阵 我在 Python 和 jQuery 中找到了很好的解决方案 但在 Java 中却没有 只有通过 jsoup 的非常简单的表 XSLT 有一种很好的

  • 如何交替两个数组中的字符？

    我需要帮助弄清楚如何组合两个字符数组 然后让元素在新数组中交替 给定的数组可以是不同的长度 例如 char1 B D char2 c R 5 输出应为 char3 B c D r 5 char ch3 new char ch1 length

  • 使用 Mean Shift 进行图像分割的解释

    谁能帮我理解 Mean Shift 分割的实际工作原理吗 这是我刚刚制作的一个 8x8 矩阵 103 103 103 103 103 103 106 104 103 147 147 153 147 156 153 104 107 153 1

  • 在 JavaScript 中检查数组是否包含 null 以外的内容？

    我有一个数组 很可能总是这样 null null null null null 有时这个数组可能会变成这样 helloworld null null null null 我知道我可以使用 for 循环 但是有没有办法使用indexOf检查数

  • 按第二个值对二维数组进行排序

    好吧 假设我有一个像 z 1 d 3 e 2 这样的数组 如何按每个组成数组的第二个元素对该数组进行排序 这样我的数组就会如下所示 z 1 e 2 d 3 arr z 1 d 3 e 2 arr sort a b a 1 lt gt b 1

  • 从一个 numpy 数组中删除另一个 numpy 数组中的元素的有效方法

    从一个 numpy 数组中删除另一个数组中的元素的最佳方法是什么 本质上我是在追求np delete 其中数组的顺序并不重要 import numpy as np a np array 2 1 3 print a b np array 4

  • 在Matlab中将矩阵中的元素i,j设置为i*j

    我想生成一个矩阵 其中 i j 元素等于 i j 其中 i j e g 0 2 3 2 0 6 3 6 0 到目前为止 我已经发现我可以使用这个索引矩阵访问非对角线元素 idx 1 eye 3 但我还没有弄清楚如何将矩阵单元的索引合并到计算

随机推荐

  • NPAPI 插件之上的 HTML

    在我使用 FireBreath 和 OpenGL 编写完浏览器插件并使用对象标签嵌入插件后 我尝试在插件之上覆盖各种 HTML 元素 不幸的是 无论我如何尝试 标签和插件图形始终位于页面上任何其他 HTML 元素的顶部 据我所知 flash

  • 使用 awk 在数字和数字之间转换月份

    在过去的考试试卷中 我有一个问题 月份可以用不同的方式表示 例如数字 1 2 12 或三字母月份名称 Jan Feb Dec 建议如何使用 awk 中的关联数组来转换 三个字母的月份名称到月份数字 反之亦然 到 将月份数字翻译为三个字母的月

  • nodejs - mongodb - 如何找到所有a！= b？

    这是征集会 id R65i3SmvucW9imK2cxA6wdFb GXoSHjly7obzFNslklNCBvE0UrW qOiNmiBtPN24 1c session channel all username xuka expires

  • STL 容器分配放置新

    我找不到这个问题的确切答案 因此在这里发帖 当我想到向量时 它需要在连续的内存位置构建对象 这意味着向量保持分配的内存 并且必须对推入其中的对象进行就地构造 放置新的 这是一个有效的假设吗 另外 这是否意味着容器正在手动调用析构函数而不是调

  • 如何使用 lxml 从此 HTML 片段获取文本？

    谁能解释为什么这个片段在断言上失败 from lxml import etree s div h2 img XYZZY h2 div root etree fromstring s elements root xpath contains

  • asp.net core 运行时标签中的 6 个奇怪属性

    我有一个 VS2022 asp net core 6 Web 应用程序 运行时许多 Layout cshtml 标记中的 html 标记属性 b g6ltozs93r 无效 这是一个未受影响的项目的示例 VS2019 net5 或更早版本不

  • 发送短信和彩信

    我正在考虑用我自己的应用程序替换默认的 Android 短信应用程序 但我不完全知道如何发送短信和彩信短信 我想至少得到它 以便我可以先发送短信 因为我认为发送彩信会困难得多 那么 发送这些类型的消息时具体应该怎么做呢 有没有足够容易理解的

  • 我应该在 1.x、2.2 和 0.23 中选择哪个 hadoop 版本

    您好 我是 Hadoop 新手 对版本名称非常困惑 我应该使用 1 x 强大的支持和学习资源 2 2 或 0 23 中的哪一个 我读到 hadoop 正在从 v0 23 完全迁移到 YARN link1 但与此同时 整个网络都在说 hado

  • 为什么HTML标签在elasticsearch中被过滤掉了还是可搜索的

    我是 elasticsearch 的新手 正在测试 html strip 过滤器 理想情况下 我不应该能够搜索 HTML 标签 以下是步骤 Index curl XPOST localhost 9200 foo test analyzer

  • MATLAB 中的绘图函数

    我在 Matlab 中绘制以下函数时遇到问题 x 10 sin pi f 0 1 pi f 0 1 2 我正在使用这段代码 f 50 0 1 50 x 10 sin pi f 0 1 pi f 0 1 2 plot f x 我可以使用在 g

  • 在所选文件中找不到从 DbContext 派生的可构造类型 (EF Power Tools Beta 2 + VS 2012))

    我将 VS 2012 Ultimate 与 Entity Framework Power Tools Beta 2 和实体框架 5 0 使用 nuget 一起使用 我创建了一个 DbContext 类 当我右键单击解决方案资源管理器中的相应

  • 将列转换为行的 SQL 查询

    我有一个如下所示的表格 我的问题是 如何将列转换为行 我正在使用 Microsoft SQL Server sip RECno user1 user2 user3 user4 1 ram ravi sam raj 我需要像下面这样的操作 u

  • 具有任意排序功能的 NSSortDescriptor

    我无法理解如何使用 NSSortDescriptor 进行任意排序 我想做这样的事情 NSArray sortAlgorithm NSArray arrayWithObjects r a nil NSSortDescriptor sortD

  • 具有自定义授权者和 CORS 的 AWS API Gateway 间歇性 200 然后 403 然后 200 ...奇怪

    我有一个带有自定义授权者的 1 Amazon Api Gateway 设置 授权者基本上只返回允许任何内容 我启用了 CORS 这是从jQuery网页 我有两个方法 vehicles 返回汽车列表 bookings 返回预订详细信息 我看到

  • 结果集中重复检索返回null

    我有一个问题ResultSet getString当我第一次调用它时 它返回值 但第二次返回 null 这不会关闭结果集或 sql 连接 if rs getString i null properties setProperty metaD

  • 我是否需要删除传递给 google protocol buffer (protobuf) 的对象？

    我有简单的消息 message SmallValue int32 val 1 message Value int32 val1 1 int32 val2 2 SmallValue val3 3 message SendMessage int

  • 从函数获取多个值，而无需在 LUA 中创建变量

    有没有办法从函数中获取多个值而不为其创建变量 local major minor revision codename love getVersion Get current L VE version as a string 因此 我们不会使

  • 受保护成员范围

    我正在为 SCJP 做准备 我还知道受保护的成员范围位于包内以及其他包中 并且具有某些条件 例如只能通过继承来实现 例如 我有三个班级 家长班 孩子班 朋友班 package x parent class Parentclass prote

  • python 2-D列表如何制作一组[重复]

    这个问题在这里已经有答案了 作为一个Python列表如下 list1 1 2 3 4 1 2 我想制作一套 这样我就可以列出独特的项目 例如 list2 1 2 3 4 python中有一些我可以使用的函数吗 谢谢 那会做 gt gt gt

  • 是否有可能在 O(n) 时间内找到给定数组中的所有三元组？

    给定一个数字数组 找到满足给定条件的所有三元组 健康 状况 a i lt a j lt a k where I lt j lt k 有可能在O n 时间内解决这个问题吗 这不是家庭作业 输出的大小 最坏情况 是复杂性的下限 由于可能存在 O

热门标签