javascript - Peak and Flag Codility 最新挑战

Question

我正在尝试解决最新的 codility.com 问题(只是为了提高我的技能)。我试过分配但没有得到超过 30 分，所以现在很好奇我的解决方案中到底缺少什么。

问题是

给定一个由 N 个整数组成的非空零索引数组 A。峰是一个数组元素，它比它的邻居大。更准确地说，它是一个索引 P，使得

0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1]

例如下面的数组A:

A[0] = 1 
A[1] = 5 
A[2] = 3 
A[3] = 4 
A[4] = 3 
A[5] = 4 
A[6] = 1 
A[7] = 2 
A[8] = 3 
A[9] = 4 
A[10] = 6 
A[11] = 2

恰好有四个峰:元素 1、3、5 和 10。

你要去一系列山脉旅行，其相对高度由数组 A 表示。你必须选择你应该带多少旗帜。目标是根据特定规则在山峰上设置最大数量的标志。

只能在峰上设置标志。另外，如果取K个flags，那么任意两个flags之间的距离应该大于等于K。索引P和Q之间的距离是绝对值|P − Q|。

例如，给定上面数组 A 表示的山脉，N = 12，如果您采用:

> two flags, you can set them on peaks 1 and 5; 

> three flags, you can set them on peaks 1, 5 and 10; 

> four flags, you can set only three flags, on peaks 1, 5 and 10.

因此在这种情况下您最多可以设置三个标志。

编写一个函数，给定一个包含 N 个整数的非空零索引数组 A，返回可以在数组的顶点上设置的最大标志数。例如，给定上面的数组

函数应该返回 3，如上所述。

假设:

N为[1..100,000]范围内的整数；

数组A的每个元素都是[0..1,000,000,000]范围内的整数。

复杂度:

预期的最坏情况时间复杂度为 O(N)；预期的最坏情况空间复杂度为 O(N)，超出输入存储(不计算输入参数所需的存储空间)。

所以我根据我对问题的理解尝试了这段代码

var A = [1,5,3,4,3,4,1,2,3,4,6,2];

function solution(A) {
 array = new Array();  
   for (i = 1; i < A.length - 1; i++) {  
    if (A[i - 1] < A[i] && A[i + 1] < A[i]) {  
     array.push(i);  
    }  
   }  

  //console.log(A);
  //console.log(array);
  var position = array[0];
  var counter = 1;
  var len = array.length;
  for (var i = 0; i < len; i++) {
    if (Math.abs(array[i+1] - position) >= len) {
        position = array[i+1];
        counter ++;
        }
    }

  console.log("total:",counter);
  return counter;

}

以上代码适用于示例数组元素:[1,5,3,4,3,4,1,2,3,4,6,2]在索引处获取峰值:[1, 3, 5, 10] 并在 1、5 和 10(总共 3 个)处设置标志

但是 codility.com 说它在数组 [7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7] 上失败了我的代码在索引处达到峰值:[1, 4, 6, 8] 并将标志设置为 1 和 6(总共 2 个)但 coditity.com 说它应该是 3 个标志。 (不知道为什么)我是否误解了这个问题？

拜托，我只是在寻找提示/算法。我知道这个问题已经被某人问过并在私有(private)聊天室中解决了，但在那个页面上我试图从那个人那里获得帮助但成员们宁愿将我的帖子标记为不合适的答案所以我在这里再次问这个问题。

P.S:您可以尝试自己编写挑战代码 here !

Answer 1

这是一个具有更好复杂性上限的解决方案:

• 时间复杂度:O(sqrt(N) * log(N))
• 空间复杂度:O(1) (在原始输入存储上)

Python 实现

from math import sqrt

def transform(A):
    peak_pos = len(A)
    last_height = A[-1]
    for p in range(len(A) - 1, 0, -1):
        if (A[p - 1] < A[p] > last_height):
            peak_pos = p
        last_height = A[p]
        A[p] = peak_pos
    A[0] = peak_pos

def can_fit_flags(A, k):
    flag = 1 - k
    for i in range(k):
        # plant the next flag at A[flag + k]
        if flag + k > len(A) - 1:
            return False
        flag = A[flag + k]
    return flag < len(A)  # last flag planted successfully

def solution(A):
    transform(A)
    lower = 0
    upper = int(sqrt(len(A))) + 2
    assert not can_fit_flags(A, k=upper)
    while lower < upper - 1:
        next = (lower + upper) // 2
        if can_fit_flags(A, k=next):
            lower = next
        else:
            upper = next
    return lower

描述

O(N)预处理(就地完成):

A[i] := next peak or end position after or at position i
        (i for a peak itself, len(A) after last peak)

如果我们能种植k旗帜然后我们当然可以种植k' < k旗帜也是如此。如果不能种植k插旗那我们肯定不能种k' > k旗帜。我们总是可以设置 0 个标志。让我们假设我们不能设置 X旗帜。现在我们可以使用二分查找来找出究竟可以插多少旗。

Steps:
  1. X/2
  2. X/2 +- X/4
  3. X/2 +- X/4 +- X/8
  ...
  log2(X) steps in total

经过之前的预处理，每一步检测是否k可以插旗可以在O(k)中执行操作:

• 标志(0)=下一个(0)
• 标志(1)=下一个(标志(1)+ k)...
• 标志(k-1)=下一个(标志(k-2)+ k)

总成本 - 最坏情况 - 当 X - 1可以插旗:

== X * (1/2 + 3/4 + ... + (2^k - 1)/(2^k))
== X * (log2(X) - 1 + (<1))
<= X * log(X)

使用 X == N会起作用，而且很可能也是次线性的，但不足以证明该算法的总上限低于 O(N)。 .

现在一切都取决于找到一个好的X , 它自 k旗帜大约需要 k^2适合的位置，似乎应该在 sqrt(N) 附近找到一个很好的标志数量上限。 .

如果X == sqrt(N)或接近它的东西起作用，然后我们得到 O(sqrt(N) * log(sqrt(N))) 的上限这绝对是次线性的，因为 log(sqrt(N)) == 1/2 * log(N)该上限相当于 O(sqrt(N) * log(N)) .

让我们在 sqrt(N) 附近寻找所需标志数量的更精确上限:

• 我们知道k标志需要 Nk := k^2 - k + 3旗帜
• 通过求解方程 k^2 - k + 3 - N = 0在 k我们发现如果 k >= 3 , 然后任意数量的标志 <= 结果 k可以适合一些长度为 N 的序列，而更大的则不能；该方程的解是1/2 * (1 + sqrt(4N - 11))
• N >= 9我们知道我们可以放 3 面旗帜==> 对于 N >= 9 , k = floor(1/2 * (1 + sqrt(4N - 11))) + 1是我们可以容纳的标志数量的严格上限 N
• N < 9我们知道 3 是一个严格的上限，但这些情况与我们寻找大 O 算法复杂度无关

floor(1/2 * (1 + sqrt(4N - 11))) + 1
== floor(1/2 + sqrt(N - 11/4)) + 1
<= floor(sqrt(N - 11/4)) + 2
<= floor(sqrt(N)) + 2

==> floor(sqrt(N)) + 2对于可以放入 N 中的许多标志也是一个很好的严格上限元素 + 这个甚至适用于 N < 9所以它也可以在我们的实现中用作通用的严格上限

如果我们选择X = floor(sqrt(N)) + 2我们得到以下总算法上限:

O((floor(sqrt(N)) + 2) * log(floor(sqrt(N)) + 2))
   {floor(...) <= ...}
O((sqrt(N) + 2) * log(sqrt(N) + 2))
   {for large enough N >= 4: sqrt(N) + 2 <= 2 * sqrt(N)}
O(2 * sqrt(N) * log(2 * sqrt(N)))
   {lose the leading constant}
O(sqrt(N) * (log(2) + loq(sqrt(N)))
O(sqrt(N) * log(2) + sqrt(N) * log(sqrt(N)))
   {lose the lower order bound}
O(sqrt(N) * log(sqrt(N)))
   {as noted before, log(sqrt(N)) == 1/2 * log(N)}
O(sqrt(N) * log(N))
                                  QED