javascript - JavaScript 中的 Codility Leader 算法

Question

我正在尝试用 JavaScript 解决 Codility 'Leader' 问题。

题目如下:

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

A[0] = 3    A[1] = 4    A[2] =  3
A[3] = 2    A[4] = 3    A[5] = -1
A[6] = 3    A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in > those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function function solution(A); that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

A[0] = 3    A[1] = 4    A[2] =  3
A[3] = 2    A[4] = 3    A[5] = -1
A[6] = 3    A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];and each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

我的答案如下:

function solution(A) {
    const length = A.length
    if (length > 100000) return -1
    const counters = new Array(length).fill(0)
    const negativeCounters = new Array(length).fill(0)
    for (i=0; i < length; i++){
        if (A[i] < -2147483648 || A[i] > 2147483647) return -1
        if (A[i] > -1){
            counters[A[i]] = counters[A[i]] + 1
            if (counters[A[i]] > (length / 2)) return i
        } else {
            negativeCounters[A[i] * -1]  =  negativeCounters[A[i] * -1] + 1
            if (negativeCounters[A[i] * -1] > (length / 2)) return i
        }
    }
    return -1
}

虽然我已经尝试了各种成功的输入，但它没有通过正确性测试。 Codility 评估未列出测试输入，因此我找不到破坏算法的输入。

谁能发现问题？

Answer 1

与一些评论和一个答案相反，实际上在 JavaScript 中使用一组计数器工作正常。这是因为 JavaScript 中的数组是关联对象。您的代码存在一个问题，即无法将键/索引大于初始计数器数组长度的计数器初始化为零。

以下代码在 Codility 的所有指标上都达到了 100%:

function solution(A) {
    const arr = []
    for (let i=0; i<A.length; i++){
      if (!arr[A[i]])
        arr[A[i]] = 1
      else
        arr[A[i]]++
      if (arr[A[i]] > A.length/2)
        return i
    }
    return -1
}