计数不可分割 - 同志训练任务

arrays algorithm java training-data

2022-09-03 17:10:53

我现在正在折磨溺爱。有些任务我可以自己解决，但有些任务有问题。这项任务的难度<**>。它是中等的，但我停滞不前。

问题：

您将获得一个由 N 个整数组成的非空零索引数组 A。对于每个数字 A[i]，使得 0 ≤ i < N，我们要计算数组中不是 A[i] 除数的元素数。我们说这些元素是非除数。例如，考虑整数 N = 5 和数组 A，以便：

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6

对于以下元素：

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.

编写一个函数：

class Solution { public int[] solution(int[] A); }

给定一个由 N 个整数组成的非空零索引数组 A，返回一个表示非除数数的整数序列。该序列应返回为：

结构结果（在 C 中），
或整数向量（以C++为单位），
或记录结果（以帕斯卡为单位），
或整数数组（在任何其他编程语言中）。

例如，给定：

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 3
A[4] = 6

该函数应返回 [2， 4， 3， 2， 0]，如上所述。假设：

N 是 [1..50，000] 范围内的整数;
数组 A 的每个元素都是 [1..2 * N] 范围内的整数。

复杂性：

预期的最坏情况时间复杂度为O（N*log（N））;
预期的最坏情况空间复杂度为 O（N），超出输入存储范围（不计算输入参数所需的存储）。

可以修改输入数组的元素。

我已经写了一些解决方案。但是我的解决方案体积庞大，仍然具有O（n^2）复杂性。你能帮我一些想法或算法如何以最佳方式做到这一点吗？这不是面试任务或其他东西。我只是在训练，并试图解决所有任务。您可以在此处找到此任务：http://codility.com/demo/train/ 第 9 课，第一课中的第一个任务。

谢谢！

答案 1

我想我会在C++分享我的解决方案，它得到了100分。我认为这很简单。

https://codility.com/demo/results/demoQFK5R5-YGD/

首先，它计算数组中每个数字的出现次数。
然后，对于每个数组元素，它找到从 1 到的范围内的除数，包括除数，这是除法的结果。isqrt(i)

最后，它从数组中的元素总数中减去给定元素的除数总数。

vector<int> solution(vector<int> &A) {

    int N = A.size();
    vector<int> counts (*std::max_element(A.begin(), A.end()) + 1,0);

    // Calculate occurences of each number in the array
    for (int i = 0; i < N; ++i)
    {
        counts[A[i]] += 1;
    }

    std::vector<int> answer(N,0);

    // For each element of the array
    for (int i = 0; i < N; ++i)
    {
        // Calulate how many of its divisors are in the array
        int divisors = 0;

        for (int j = 1; j * j <= A[i]; ++j)
        {
            if (A[i] % j == 0)
            {
                divisors += counts[j];
                if (A[i] / j != j)
                {
                    divisors += counts[A[i] / j];
                }
            }
        }

        // Subtract the number of divisors from the number of elements in the array
        answer[i] = N - divisors;
    }

    return answer;
}

答案 2

此解决方案给出 100 分。https://codility.com/demo/results/demo63KVRG-Q63/

public int[] solution(int[] A) {
    int[][] D = new int[A.length*2 + 1][2];

    for (int i = 0; i < A.length; i++) {
        D[A[i]][0]++;
        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 <= Math.sqrt(A[i]) ; j++) {
                if (A[i] % j == 0 && A[i] / j != j) {
                    D[A[i]][1] += D[j][0];
                    D[A[i]][1] += D[A[i]/j][0];
                } else if (A[i] % j == 0 && A[i] / j == j) {
                    D[A[i]][1] += D[j][0];
                }
            }
        }
    }
    for (int i = 0; i < A.length; i++) {
        A[i] = A.length - D[A[i]][1];
    }
    return A;
}

谢谢大家的帮助。