在数组中查找三个数字的算法，使得 a< b < c 和 v[a]

转载 作者：塔克拉玛干 更新时间：2023-11-03 04:20:57 26 4

给定一个整数向量，我需要找出是否存在三个元素 a, b, c在向量中 a < b< c和 v[a] < v[c] < v[b] .

到目前为止，我的方法如下。首先，我忘记了 a 并为向量中的每个数字找到位于该元素左侧的 v[i] 的最小值。我将此信息存储在另一个数组中。然后我应用合并排序，当我到达两个元素交叉的点时，我测试右边的元素是否可以是 c 而左边的元素是 b。但是，我还需要测试与正确元素交叉的其他元素是否可以是b，这增加了太多的时间复杂度。我最多需要它是线性的。你能给我一个关于如何继续的提示吗？

编辑:请原谅，之前的标题不对。我需要的是 a < b < c 和 v[a] < v[c] < v[b]

EDIT2: 限制:除了向量之外，我不能使用数据结构。并且算法必须基于分而治之的方法。

最佳答案

您可以在 O(n) 时间和最坏的 O(n) 时间内完成此操作通过遍历数组同时维护最大禁止范围(v[a]、v[c])的堆栈(后进先出数据结构)。堆栈的最顶层元素是从目前看到的最小值到该最小值之后看到的最大值的范围。 (或者，出于实现原因，您可能会发现将该范围保存在单独的变量中更容易，并且仅将堆栈用于旧禁止范围。)

处理任何单个元素最多可能需要 O(n) 时间(如果它必须展开整个堆栈一直回到第一个范围)，但是这个成本必须摊销，这样处理整个数组仍然只有 O(n) 时间(因为处理一个元素会展开整个堆栈的唯一原因是如果它将所有禁止范围统一为一个更大的范围，在这种情况下，它不需要重新添加它弹出的所有范围，因此该工作仅完成一次) .

关于在数组中查找三个数字的算法，使得 a< b < c 和 v[a]<v[c]<v[b]，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53583796/

26 4 0

• ios - Swift:将 [A, B, B, B, A, B, B, B] 数组转换为哈希数组 [ [A: [B, B, B], [A: [B, B, B] ] ]

  我有两种结构，Header 和Session，它们都符合协议(protocol)TimelineItem。 我有一个 Array 由 TimelineItem 组成，如下所示: [Header1, S

• python - 斐波那契的 `a, b = b, a+b` 和 `a = b; b = a+b` 有什么区别

  这个问题在这里已经有了答案: Multiple assignment and evaluation order in Python (11 个答案) 关闭 6 年前。 我刚接触python所以想问你

• R 问题 A、A、A、A、B、B、B、B、B 的唯一组合数

  我试图找到一种方法来在 R 中获取 A、A、A、A、B、B、B、B、B 的所有可能的唯一排列的列表。 组合最初被认为是获得解决方案的方法，因此组合的答案。 最佳答案 我认为这就是你所追求的。 @bil

• clojure - 混合两个向量 : [a a] and [b b] to [a b a b]

  我怎样才能将两个给定的向量混合成一个新的向量，它以交替的顺序保存它们的值。 (f [a a] [b b]) ; > [a b a b] 这是我想到的: (flatten (map vector [:a

• Python a, b = b, a + b

  这是我的第一个问题，我开始学习Python。之间有区别吗: a, b = b, a + b 和 a = b b = a + b 当您在下面的示例中编写它时，它会显示不同的结果。 def fib(n):

• c++ - A::B::B::B::B...B::f() 对吗？为什么我可以这样做？

  这个问题在这里已经有了答案: Why is there an injected class name? (1 个回答) 12 个月前关闭。 我不知道如何解释: namespace A { struct

• java - 为什么 "a^=b^=a^=b;"与 "a^=b; b^=a; a^=b;"不同？

  我尝试了一些代码来交换 Java 中的两个整数，而不使用第三个变量，使用 XOR。 这是我尝试过的两个交换函数: package lang.numeric; public class SwapVars

• java - B b 和 A b 之间的区别

  假设类 B 扩展类 A，并且我想为 B 声明一个变量。什么更有效？为什么？ B b或 A b . 最佳答案 您混淆了两个不同的概念。 class B extends A { } 意味着B 是 A .

• Python(斐波纳奇数列): trying to understand what is the difference between a, b = b, a + b OR a = b & a = a + b

  我不确定这个问题的标题是什么，这也可能是一个重复的问题。所以请相应地指导。 我是 python 编程的新手。我有这个简单的代码来生成斐波那契数列。 1: def fibo(n): 2: a =

• c++ - 我无法理解 c 风格转换之间的区别(例如 :- A a;B *b;b = (*B) (&a);) and dynamic_cast(&a);

  我在谷歌上搜索了有关 dynamic_cast 的内容，我发现显式地将基类对象转换为派生类指针可能是不安全的。但是当我运行一些示例代码来检查它时，我没有收到任何错误。请在下面找到我的代码: class

• c++ - "B(int b=0):b(b){}"是什么意思？

  这个问题在这里已经有了答案: What is this weird colon-member (" : ") syntax in the constructor? (14 个答案) 关闭 8 年前。

• sql - 测试非整数是否在 [a,b) - 或 [a,b], (a,b), (a,b] 范围内

  在不重现产生非整数值的表达式的情况下实现以下目标的惯用方法是什么(在我的真实情况下，该值是在我不想重现的冗长查询之后计算为百分比的): SELECT * FROM SomeTable WHERE 1/

• javascript - [b,a] =[a,b] 和 const [b,a]=[a,b] 有什么区别

  在析构中，这两个代码的结果确实不同。我不确定为什么。 提示说 const [b,a] = [a,b] 将导致 a,b 的值为 undefined (从左到右的简单分配规则)。我不明白为什么会这样。 l

• c++ - 为什么使用 “b < a ? a : b” 而不是 “a < b ? b : a” 来实现最大模板？

  C++ Templates - The Complete Guide, 2nd Edition介绍max模板: template T max (T a, T b) { // if b < a th

• Java取模概念——算术定义(a/b)*b+(a%b)

  我最近开始学习代码(Java)，并根据第 15.17.3 节在 Oracle 网站上查找了模运算符。以下链接: http://docs.oracle.com/javase/specs/jls/se8/

• pointers - 这种指针用法有什么区别(a :=&A; a) and (b:=B; &b)

  无法理解以下行为。 d1 := &data{1}; 的区别d1 和 d2 := 数据{1}； &d1。两者都是指针，对吧？但他们的行为不同。这里发生了什么 package main import "f

• java - "a <= b && b <= a && a != b"怎么可能是真的？

  这个问题在这里已经有了答案: How to make loop infinite with "x = y && x != y"? (4 个回答) How can i define variables

• python - python 中的 ['[a,a,a]' ,'[b,b,b]' ] 和 [[a,a,a],[b,b,b]] 有什么区别？

  在我的程序中，当我调试我的代码时，它似乎在我生成的代码中的某处 X1=['[a,a,a]','[b,b,b]'] 还有我生成的其他地方 X2=[[a,a,a],[b,b,b]] 当我想添加这两个列表然

• c++ - 鉴于 b 始终非零，为什么 `b ? --b :++b` 有效，但 `--b` 无效？

  我试图使用递归将两个整数相乘，并意外编写了这段代码: //the original version int multiply(int a, int b) { if ( !b ) retu

• python - 如何对 python 说 (a+b) = (b+a) 和 (a*b) = (b*a)

  我有一个列表中数字之间所有可能的操作组合: list = ['2','7','8'] 7+8*2 8+7*2 2*8+7 2+8*7 2-8*7 8-2/7 etc 我想知道是否可以说像 ('7*2+