javascript - 解决 CountNonDivisible 代码问题

Question

我正在处理 Codility 问题，并且正在处理“CountNonDivisible”问题。我尝试了粗暴的工作方式，但效率很低。

我找到了没有解释的答案，所以如果有人能花一些时间引导我完成这个答案，我将不胜感激。

function solution(A) {
    const lenOfA = A.length
    const counters = Array(lenOfA*2 + 1).fill(0)
    for(let j = 0; j<lenOfA; j++) counters[A[j]]++;
    
    return A.map(number=> {
        let nonDivisor = lenOfA
        for(let i = 1; i*i <= number; i++) {
            if(number % i !== 0) continue;
            nonDivisor -= counters[i];
            if(i*i !== number) nonDivisor -= counters[number/i]
        }
        return nonDivisor
    })
}

这就是问题

Task description

You are given an array A consisting of N integers.

For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.

For example, consider integer N = 5 and array A such that: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6

For the following elements:

    A[0] = 3, the non-divisors are: 2, 6,
    A[1] = 1, the non-divisors are: 3, 2, 3, 6,
    A[2] = 2, the non-divisors are: 3, 3, 6,
    A[3] = 3, the non-divisors are: 2, 6,
    A[4] = 6, there aren't any non-divisors.

Write a function:

function solution(A);

that, given an array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.

Result array should be returned as an array of integers.

For example, given: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 3 A[4] = 6

the function should return [2, 4, 3, 2, 0], as explained above.

Write an efficient algorithm for the following assumptions:

    N is an integer within the range [1..50,000];
    each element of array A is an integer within the range [1..2 * N].

Answer 1

这是我可以解释上述解决方案的一种方式。

从挑战描述中可以看出，数组的每个元素都在 [1...2*N] 范围内，其中 N 是数组的长度；这意味着数组中的任何元素都不能大于 2*N。

因此创建了一个长度为 2*N + 1 的计数器数组(最大索引等于数组中的最大可能值)，并且其中的每个元素都初始化为 0，除了给定数组中实际存在的元素，这些设置为 1。

现在我们要遍历给定数组中的所有元素，假设每个数字都是非因数，并将假定的非因数减去计数器数组中的除数数，这将给出实际的非因数数。在循环过程中，当我们的数组中不存在的元素是除数时，我们减去 0(记住我们的初始化值)，当我们遇到也在我们的数组中的除数时，我们减去 1(记住我们的初始化值)值)。对数组中的每个元素执行此操作，以获得其每个非除数计数。

您发布的解决方案使用了映射，这只是一种转换数组的简洁方法。也可以使用简单的 for 循环，这样会更容易理解。这是上述解决方案的 for 循环变体

  function solution(A) {
    const lenOfA = A.length
    const counters = Array(lenOfA*2 + 1).fill(0)
    for(let i = 0; i<lenOfA; i++) counters[A[i]]++;

    const arrayOfNondivisors = [];

    for(let i = 0; i < A.length; i++) {
      let nonDivisor = lenOfA
        for(let j = 1; j*j <= A[i]; j++) {
            if(A[i] % j !== 0) continue;
            nonDivisor -= counters[j];
            if(j*j !== A[i]) nonDivisor -= counters[A[i]/j]
        }
        arrayOfNondivisors.push(nonDivisor);
    }
    
    return arrayOfNondivisors;
}