java - CountNonDivisible - コディリティ トレーニング タスク

Question

私は今、コディリティのトレーニングをしています。自分で解決できるタスクもありますが、一部のタスクには問題があります。このタスクの難易度は<**>です。ミディアムですが、失速しました。

問題：

---

N 個の整数で構成される、空でないゼロ インデックスの配列 A が与えられます。0 ≤ i < N のような各数値 A[i] について、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

100 点を獲得する C++ のソリューションを共有すると思いました。とてもわかりやすいと思います。

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

1. 最初に、配列内の各数値の出現回数をカウントします。

2. 次に、各配列要素について、除算の結果である除数を含めて、i1 から までの範囲で除数の数を見つけます。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

このソリューションは 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;
}

ご協力ありがとうございました。

Answer 3

これが私の100スコアのPythonソリューションです。それが他の人に役立つことを願っています。

def solution(A):
    ''' Solution for the CountNonDivisible by codility
        Author: Sheng Yu - codesays.com
    '''
    from math import sqrt

    A_max = max(A)
    A_len = len(A)

    # Compute the frequency of occurrence of each
    # element in array A
    count = {}
    for element in A:
        count[element] = count.get(element,0)+1

    # Compute the divisors for each element in A
    divisors = {}
    for element in A:
        # Every nature number has a divisor 1.
        divisors[element] = [1]
    # In this for loop, we only find out all the
    # divisors less than sqrt(A_max), with brute
    # force method.
    for divisor in xrange(2, int(sqrt(A_max))+1):
        multiple = divisor
        while multiple  <= A_max:
            if multiple in divisors and not divisor in divisors[multiple]:
                divisors[multiple].append(divisor)
            multiple += divisor
    # In this loop, we compute all the divisors
    # greater than sqrt(A_max), filter out some
    # useless ones, and combine them.
    for element in divisors:
        temp = [element/div for div in divisors[element]]
        # Filter out the duplicate divisors
        temp = [item for item in temp if item not in divisors[element]]
        divisors[element].extend(temp)

    # The result of each number should be, the array length minus
    # the total number of occurances of its divisors.
    result = []
    for element in A:
        result.append(A_len-sum([count.get(div,0) for div in divisors[element]]))

    return result

Answer 4

ハッシュマップを使用し、o(nlogn) および o(n) の時間と空間の複雑さを満たします

import java.util.*;

class Solution {

    public int[] solution(int[] A) {

        int N = A.length;
        HashMap<Integer, Integer> count = new HashMap<>();

        for (int i : A) {
            Integer key = count.get(i);
            if (key != null) {
                count.put(i, key + 1);
            } else {
                count.put(i, 1);
            }
        }

        HashMap<Integer, Integer> divs = new HashMap<>();
        for (Integer n : count.keySet()) {
            int sum = 0;
            int j = 1;
            while (j * j <= n) {
                if (n % j == 0) {
                    if (count.containsKey(j)) {
                        sum += count.get(j);
                    }
                    //find n = j*k cases to add both to the dividors
                    int k = n / j;
                    if (k != j) {
                        if (count.containsKey(k)) {
                            sum += count.get(k);
                        }
                    }
                }
                j++;
            }

            divs.put(n, N - sum);
        }

        for (int i = 0; i < A.length; i++) {
            A[i] = divs.get(A[i]);
        }

        return A;
    }
}

Answer 5

C# でのこの 100/100 コード ソリューション。C# と Java は非常に似ているため、役立つ場合があります。

 public class NonDivisiblesCounter
{
    /// <summary>
    /// 1. Count the ocurrences of each element
    /// 2. Count all divisors for each element and subtract by the Length of array A to get nonDivisors
    /// 3. Add it to a cache since the elements can repeat and you do not need to calculate again.
    /// </summary>
    /// <param name="A"></param>
    /// <returns></returns>
    public int[] Count(int[] A)
    {
        int n = A.Length;
        var ocurrencesOfEach = CountOcurrencesOfEach(A);
        var nonDivisorsOfEach = new int[n];
        var nonDivisorsCache = new Dictionary<int, int>();

        for (int i = 0; i < n; i++)
        {
            int element = A[i];

            if (nonDivisorsCache.ContainsKey(element))
            {
                nonDivisorsOfEach[i] = nonDivisorsCache[element];
            }
            else
            {
                int nonDivisorCounter = n - CountDivisorsPerOcurrence(element, ocurrencesOfEach);
                nonDivisorsOfEach[i] = nonDivisorCounter;
                nonDivisorsCache[element] = nonDivisorCounter;
            }
        }

        return nonDivisorsOfEach;
    }

    private int CountDivisorsPerOcurrence(int element, Dictionary<int, int> ocurrencesOfEach)
    {
        int square = (int)Math.Sqrt(element);
        int divisorCounter = 0;

        if (square * square == element && ocurrencesOfEach.ContainsKey(square))
        {
            divisorCounter += ocurrencesOfEach[square];
        }

        for (int divisor = 1; element / divisor > square; divisor++)
        {
            if (element % divisor == 0)
            {
                if (ocurrencesOfEach.ContainsKey(divisor))
                {
                    divisorCounter += ocurrencesOfEach[divisor];
                }

                if (ocurrencesOfEach.ContainsKey(element / divisor))
                {
                    divisorCounter += ocurrencesOfEach[element / divisor];
                }
            }
        }

        return divisorCounter;
    }

    private Dictionary<int, int> CountOcurrencesOfEach(int[] elements)
    {
        var result = new Dictionary<int, int>();

        for (int i = 0; i < elements.Length; i++)
        {
            int element = elements[i];

            if (result.ContainsKey(element))
            {
                result[element]++;
            }
            else
            {
                result.Add(element, 1);
            }
        }

        return result;
    }
}

Answer 6

これがjavascriptでの私の解決策です。以前のものより少し簡単で、O(n log n) で動作すると思います。ここで他のソリューションを確認できます: https://marioqs.wordpress.com

function solution(A) {
    var N = A.length;
    var count = [];
    var i;
    for (i = 0; i < 2*N+1; ++i){
        count.push(0);
    }
    for (i = 0; i < N; ++i){
        ++count[A[i]];
    }
    var divisors = [];
    for (i = 0; i < 2*N+1; ++i){
        divisors.push(0);
    } //the actual code starts here, before it's just initialisation of variables.
    i = 1;
    var k;
    while (i <= 2*N){
        k = i;
        while (k <= 2*N){
            divisors[k] += count[i];
            k += i;
        }
        ++i;
    }

    var result = [];
    for (i = 0; i < N; ++i){
        result.push(0);
    }
    for (i = 0; i < N; ++i){
        result[i] = N - divisors[A[i]];
    }
    return result;
}

Answer 7

Javascript は 100% です。https://codility.com/demo/results/demoKRRRPF-8JW/

function solution(A) {
    var N = A.length;
    if (N < 1 || N > 50000) throw 'Error: Bad input';

    var uniqueDict = {};
    var keys = [];
    for (var i = 0; i < N; ++i) {
        var num = A[i]
        var uniqueCount = uniqueDict[num];
        if (uniqueCount > 0) {
            uniqueDict[num] = uniqueCount + 1;
        } else {
            uniqueDict[num] = 1;
            keys.push(num);
        }
    }

    keys.sort(function(a,b){
        return a-b;
    });

    for (i = keys.length-1; i >= 0; --i) {
        num = keys[i];
        var divisorCount = divisors(num, uniqueDict);

        var nonDivisorCount = N - divisorCount;
        uniqueDict[num] = nonDivisorCount;
    }

    for (i = 0; i < N; ++i) {
        num = A[i];
        A[i] = uniqueDict[num];
    }
    return A;
}

function divisors(num, uniqueDict) {
    var count = 0;
    var x = 1;
    while (x * x <= num) {
        if (parseInt(num/x) === num/x) { // is divisor
            if (uniqueDict[num/x] > 0) {
                count += uniqueDict[num/x];
            }
            if (num/x !== x && uniqueDict[x] > 0) {
                count += uniqueDict[x];
            }
        }
        x++;
    }
    return count;
}

Answer 8

これが私の Java ソリューション、100% です。

モジュロなし、除算なし。「カウントソート」してふるいにかけるだけです。

public int[] solution(int[] A) {

    //find max number. To be used for 'count sort' array size.
    int max = A[0];
    for (int i = 1 ; i < A.length ; i++) {
        max = Math.max(max, A[i]);
    }

    //count sort
    int [] count = new int [max+1];
    for (int i = 0 ; i < A.length ; i++) {
        count[A[i]]++;
    }

    int [] nonDiv = new int [max+1];
    //initially count all elements as non divisible (minus 'number of occurrences' of the the given number)
    for (int i = 1 ; i < nonDiv.length; i++) {
        if (count[i] != 0) {//skip numbers which don't exists in table A
            nonDiv[i] = A.length - count[i];
        }
    }

    //sieve
    for (int i = 1 ; i < nonDiv.length; i++) {
        if (count[i] != 0) {//skip numbers which don't exists in table A
            int s = i*2;
            while (s<nonDiv.length) {
                if (nonDiv[s] != 0) {
                    //Sieve. Most important part. Decrease number of non-divisible by the number of occurrences of number 'i'.
                    nonDiv[s] -= count[i];
                }
                s+=i;
            }
        }
    }

    //produce the output
    int []res = new int [A.length];
    for (int i = 0 ; i < A.length ; i++) {
        res[i] = nonDiv[A[i]];
    }

    return res;

}

Answer 9

100% スコアの JavaScript ソリューション。Codility は複雑さが O(nlogn) であることを検出しましたが、実際には O(n * sqrt(n)) です

function solution(A) {
  const createCounts = A => {
    const counts = Array(A.length * 2 + 1).fill(0)
    for (let i = 0; i < A.length; i++) {
      counts[A[i]] += 1
    }
    return counts
  }
  const counts = createCounts(A)
  const results = []
  for (let i = 0; i < A.length; i++) {
    let nonDivisiblesCount = A.length
    let j = 1
    while (j * j < A[i]) {
      if (A[i] % j === 0) {
        nonDivisiblesCount -= counts[j]
        nonDivisiblesCount -= counts[A[i] / j]
      }
      j++
    }
    if (j * j === A[i]) {
      nonDivisiblesCount -= counts[j]
    }
    results.push(nonDivisiblesCount)
  }
  return results
}

const A = [3, 1, 2, 3, 6]
console.log(A)
const s = solution(A)
console.log(s)

Answer 10

これは、Cで100％のスコアで私にとってはうまくいきました

struct Results solution(int A[], int N) {
    struct Results result;
    // write your code in C99

    int *numbers = (int *)calloc(2*N + 1, sizeof(int));
    for (int i = 0; i < N; i++) {
        ++numbers[A[i]];
    }

    int *numbers2 = (int *)calloc(2*N + 1, sizeof(int));
    for (int i = 0; 2*i < 2*N + 1; i++) {
        if (numbers[i] != 0) {
            for (int j = 2*i; j < 2*N + 1; j+=i) {
                numbers2[j] += numbers[i];
            }
        }
    }


    int * Carr = (int *)calloc(N, sizeof(int));

    for (int i = 0; i < N; i++) {
        Carr[i] = N - numbers[A[i]] - numbers2[A[i]];
    }


    result.C = Carr;
    result.L = N;

    free(numbers);
    free(numbers2);
    return result;
}