CountNonDivisible - Codility训练任务

Question

我现在正在训练鳕鱼.我可以自己解决一些任务,但有些任务有问题.这项任务的难度是<**>.这是中等的,但我停滞不前.

问题:

---

您将获得一个由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课,课程中的第一项任务.

谢谢!

Answer 1

我以为我会用C++分享我的解决方案,获得100分.我认为这很简单.

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

1. 首先,它计算数组中每个数字的出现次数.

2. 然后对于每个数组元素i,它在1到1的范围内找到其除数的数量sqrt(i),包括除法的除数.

3. 最后,它从数组中的元素总数中减去给定元素的除数总数.

   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;
   }
   

Answer 2

解决方案尝试：（编辑，见下文）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

// Solution for Lesson 9, "CountNonDivisible"
// of http://codility.com/demo/train/
public class Solution
{
    public static void main(String[] args)
    {
        int A[] = new int[5];
        A[0] = 3;
        A[1] = 1;
        A[2] = 2;
        A[3] = 3;
        A[4] = 6;

        Solution s = new Solution();
        int B[] = s.solution(A);
        System.out.println("Input  : "+Arrays.toString(A));
        System.out.println("Result : "+Arrays.toString(B));
    }

    public int[] solution(int[] A)
    {
        Set<Integer> setA = asSet(A);
        List<Set<Integer>> divisors = computeDivisors(A.length * 2);
        int occurrences[] = computeOccurrences(A);
        int nonDivisors[] = new int[A.length];
        for (int i=0; i<A.length; i++)
        {
            int value = A[i];
            Set<Integer> d = divisors.get(value);
            int totalOccurances = 0;
            for (Integer divisor : d)
            {
                if (setA.contains(divisor))
                {
                    totalOccurances += occurrences[divisor];
                }
            }
            nonDivisors[i] = A.length-totalOccurances;
        }
        return nonDivisors;
    }


    /**
     * Returns a set containing all elements of the given array
     * 
     * Space: O(N)
     * Time: O(N)
     * 
     * @param A The input array
     * @return The set
     */
    private static Set<Integer> asSet(int A[])
    {
        Set<Integer> result = new HashSet<Integer>();
        for (int value : A)
        {
            result.add(value);
        }
        return result;
    }


    /**
     * Computes a list that contains for each i in [0...maxValue+1] a set
     * with all divisors of i. This is basically an "Eratosthenes Sieve". 
     * But in addition to setting the entries of a list to 'false' 
     * (indicating that the respective numbers are non-prime), this 
     * methods inserts the divisors into the corresponding set.
     *  
     * Space: O(N) (?)
     * Time: O(N*logN) (?)
     * 
     * @param maxValue The maximum value
     * @return The list 
     */
    private static List<Set<Integer>> computeDivisors(int maxValue)
    {
        List<Boolean> prime = new ArrayList<Boolean>();
        prime.addAll(Collections.nCopies(maxValue+1, Boolean.TRUE));
        List<Set<Integer>> divisors = new ArrayList<Set<Integer>>();
        for (int i = 0; i < maxValue + 1; i++)
        {
            Set<Integer> d = new HashSet<Integer>();
            d.add(1);
            d.add(i);
            divisors.add(d);
        }
        for (int i = 2; i <= maxValue; i++)
        {
            int next = i + i;
            while (next <= maxValue)
            {
                divisors.get(next).addAll(divisors.get(i));
                prime.set(next, Boolean.FALSE);
                next += i;
            }
        }
        return divisors;
    }

    /**
     * Computes an array of length 2*A.length+1, where each entry i contains
     * the number of occurrences of value i in array A
     * 
     * Space: O(N)
     * Time: O(N)
     * 
     * @param A The input array
     * @return The occurrences array
     */
    private static int[] computeOccurrences(int A[])
    {
        int occurances[] = new int[A.length * 2 + 1];
        for (int i=0; i<A.length; i++)
        {
            int value = A[i];
            occurances[value]++;
        }
        return occurances;
    }
}

数组中出现的数字的最大值定义为 2*arrayLength。对于数组中可能出现的每个数字，它计算

• 该数字的约数集（使用埃拉托斯特尼筛法）
• 该数字在数组中实际出现的频率

有了这些信息，我们就可以遍历数组了。对于数组中找到的每个值，可以查找除数集合，并计算所有除数出现的总数。结果就是数组长度减去除数出现的总数。

由于它仅使用埃拉托斯蒂尼筛法进行计算（并且仅遍历每个数字的除数集，该除数也应为 logN），因此它的最坏情况时间复杂度应为 O(N*logN)。但我不完全确定存储复杂度是否真的可以被认为是严格的 O(N)，因为对于 N 个数字中的每一个，它都必须存储除数的集合。也许可以通过组合一些方法来避免这种情况，但无论如何，存储空间至少也是 O(N*logN) 。

编辑：异常来自仅存储最多 A.length*2-1 值的数组，现在已修复。此外，除数集没有正确计算，现在也应该修复这个问题。除此之外，分析结果如

got      [8, 8, 9, 10, 6, 8, .. 
expected [8, 8, 9, 10, 6, 8, ..

并没有真正的帮助。也许这是“游戏”的一部分，但我现在不玩这个游戏。基本思想应该很清楚，我假设它现在可以正常工作，直到有人证明是一个反例;-P 它仍然没有达到 O(N) 存储复杂度，但我还没有想过一种可能的方法来实现这一点彻底……

Answer 3

该解决方案获得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;
}

感谢大家的帮助.