计算数组中不是每个元素的约数的元素数

Question

我试图从 Codility 中了解问题的解决方案。该问题要求计算数组中不是每个元素的约数的元素数。下面提供了完整的描述，

You are given a non-empty zero-indexed 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[6] = 6, there aren't any non-divisors.
    Write a function:
    class Solution { public int[] solution(int[] A); }
    that, given a non-empty zero-indexed array A consisting of N integers, returns a sequence of integers representing the amount of non-divisors.
    The sequence should be returned as:
    a structure Results (in C), or
    a vector of integers (in C++), or
    a record Results (in Pascal), or
    an array of integers (in any other programming language).
    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.
    Assume that:
    N is an integer within the range [1..50,000];
    each element of array A is an integer within the range [1..2 * N].
    Complexity:
    expected worst-case time complexity is O(N*log(N));
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
    Elements of input arrays can be modified.

我也有办法。

// int[] A = {3, 1, 2, 3, 6};
public static int[] solution(int[] A) {

    int[][] D = new int[2 * A.length + 1][2];
    int[] res = new int[A.length];      

        //----- 
        // 0 1 
        // 0 0 
        // 1 -1 
        // 1 -1 
        // 2 -1 
        // 0 0 
        // 0 0 
        // 1 -1 
        // 0 0 
        // 0 0 
        // 0 0 
        // 0 0
        //-----

    for (int i = 0; i < A.length; i++) {
        // D[A[i]][0]++;

        D[A[i]][0] = D[A[i]][0] + 1;
        D[A[i]][1] = -1;
    }


    for (int i = 0; i < A.length; i++){

        if(D[A[i]][1]==-1){

            D[A[i]][1]=0;

            for (int j = 1; j*j <= A[i]; j++) {

                if(A[i] % j == 0) {

                    // D[A[i]][1] = D[A[i]][1] + D[j][0];
                    D[A[i]][1] += D[j][0];

                    if (A[i]/j != j){
                        D[A[i]][1]+= D[A[i]/j][0];
                    }
                }                   
            }
        }
    }

    for (int i = 0; i < A.length; i++) {
        res[i] = A.length - D[A[i]][1]; 
    }

    return res;
}

当我试图密切关注时，我有点忘记了 for 循环内部发生的事情，

            for (int j = 1; j*j <= A[i]; j++) {

                if(A[i] % j == 0) {

                    // D[A[i]][1] = D[A[i]][1] + D[j][0];
                    D[A[i]][1] += D[j][0];

                    if (A[i]/j != j){
                        D[A[i]][1]+= D[A[i]/j][0];
                    }
                }                   
            }

例如，为什么我们需要检查像 j*j <= A[i] 这样的条件以及 if(A[i] % j == 0) 的内容。我需要解释他们为解决问题而部署的算法。

我不是懒惰，因为我已经找到了解决方案并且没有尝试。确实，我度过了愉快的时光，现在需要帮助。问题难度在网站中列为RESPECTABLE。

Answer 1

D数据structure/matrix是这样的，0th列和jth行统计数组j出现的次数A。换句话说，D[A[j]][0] 是 A[j] 的值在数组中出现的次数。

循环后，1st列和kth行计算数组中划分A[k]的元素数。换句话说，D[A[k]][1] 是数组中 A[k] 的约数。

最后结果 r[j] 就是 r[j] = (A.length) - D[A[j]][1]。因为我们想要不是除数的元素的数量。

为什么循环有效？

好吧，如果 A[i] % j == 0 那么我们要做的是计算 j 在 A 中出现的次数，然后将其添加到 D[A[i]][1]。这就是为什么你有行 D[A[i]][1] += D[j][0]; 。此外 A[i]/j 也将是一个不同的因素（除非 A[i] = j）。

数学部分用于证明集合 { A, B | A * B = N & A < sqrt(N) } = {N 的除数集}。换句话说，你必须证明所有的除数都被覆盖了（这应该很容易，但我现在太累了，想不出证明，这就是堆栈溢出）。

计算数组中不是每个元素的约数的元素数

Calculate the number of elements of an array that are not divisors of each element

java

algorithm

performance

time-complexity

space-complexity