如何在O(n)时间内求最小正邻接子序列？
共有1个答案
不可能有这样的算法。这个问题的下界是O（n log n）。我将通过把元素清晰度问题简化为它（实际上是它的非负变体）来证明它。
假设我们对这个问题有一个O(n)算法（最小非负子数组）。
我们想知道一个数组（例如a=[1,2,-3,4,2])是否只有不同的元素。为了解决这个问题，我可以用连续元素之间的差值（例如A'=[1,-5,7,-2])构造一个数组，并运行我们有的O(n)算法。原始数组仅当且仅当最小非负子数组大于0时才具有不同的元素。
-
这是一个众所周知的问题的略微修改版本，但我似乎无法理解这一点。 我们得到一个大小为n的数组，它包含无序的正数序列，没有重复项。我试图找到数组中未包含的最小正数，但我无法以任何方式对数组进行排序或编辑。整个过程应该是O（nlogn）时间和O（logn）空间的复杂性。 我能想到的所有解都是多项式时间复杂度的。
-
我在GeekforGeekshttps://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/中检查“到达终点的最小跳跃次数”问题。我对这里提到的时间复杂度感到困惑，它是O（n^n）。 如果我看到上面的代码块，minJumps（arr，I，h）递归调用是从I=l1调用的。所以在每个递归步骤中，l（
-
给定一个整数数组，其中每个元素表示可以从该元素向前执行的最大步数。编写一个函数，返回到达数组末尾（从第一个元素开始）的最小跳转次数。如果元素为0，则无法在该元素中移动。 输入： arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} 输出： 3（1- 发现了从动态规划方法到其他线性方法的多种方法。我无法理解所谓的时间线性方法。这里是一个链接，其中提出了一种线性方法。
-
我有两个关于确定2个算法的时间复杂度的问题。 用比较法从一组n个不同的数字中确定最小的3个数字。 这3个元素可以使用O(log2n)比较来确定。 O(log2n)不够，但是可以使用n+O(1)比较来确定它们。 n+O(1)不够，但是可以使用n+O(logn)比较来确定它们。 n+O(logn)不够，但是可以使用O(n)比较来确定它们。 以上都没有。 这里，我想到的方法是取3个变量（例如:min1、
-
我正在解决以下问题： null 输入：Array arr是一个非空的唯一整数列表，范围在1到1,000,000,000之间，大小N在1到1,000,000之间 输出：一个数组，其中每个索引i包含一个整数，表示ARR[i]的最大相邻子数组数 示例:arr=[3,4,1,6,2]输出=[1,3,1,5,1] 计算从1到N的每个i的g[i]是一种很有希望的方法，但我们仍然需要考虑如何尽可能有效地这样做。
-
我的看法是： 改变符号并在其中找到最大和，与我们计算最大和子数组的方法相同。改变数组中元素的符号使其处于初始状态。 如果algo有任何问题，请帮助我更正。 拐角情况：我知道如果所有元素都是正的就会有问题，我们可以通过做一些预处理来处理这种情况，即如果所有元素都是+Ve，就遍历数组，而不仅仅是从数组返回最小值。 上面提到的算法将工作，并得到DasBlinkenlight的良好支持（解释）。