CountNonDivisible - Codility培训任务

我现在正在研究编码。一些我可以自己解决的任务，但是有些任务有问题。此任务的难度是< **>。这是中等的，但我停滞了。CountNonDivisible - Codility培训任务

问题：

您给出一个非空的零索引的数组A由N个整数的。对于每个数字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); }

，给定的非 - 由零个整数组成的空索引数组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 *日志（N））;
预期最坏情况下的空间复杂度为O（N），超出输入存储（不包括输入参数所需的存储空间）。

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

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

谢谢！

来源

2014-01-20 stepler

This sounds li您应该将解决方案发布到[codereview.se]并查看他们的评论。 – Keppil

我的第一个想法是玩弄Eratosthenes的筛子，看看你是否可以用解决这个问题的方式进行按摩。我不是说这就是答案。我不知道答案是什么。这正是我的第一个想法。 – ajb

@Keppil，我的解决方案是微不足道的。用一些拐杖来解决问题是降低复杂性的显而易见的方法，但它不起作用。我没有一个好主意，所以我想专注于想法和算法，而不是代码。 – stepler

的溶液尝试：（编辑，见下文）

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。对于可能发生的阵列中的每个号码，它计算

设定该数目（使用Erathostenes筛）
多久数量实际上发生在阵列

鉴于的除数这个信息，可以遍历数组。对于在数组中找到的每个值，可以查找一组除数，然后计算所有除数的总出现次数。结果就是数组长度减去除数的总数。由于它只使用Erathostenes筛选进行计算（并且只对每个数字（也应该是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）存储的复杂性，但我没有想过实现可能的方式这彻底...

来源

2014-01-24 14:39:15 Marco13

您是否检查过您的解密方案？我试过了，并且可信性给了我这些结果https://codility.com/demo/results/demoHQAV4M-BQP/。 – stepler

添加了编辑功能，但没有编码帐户，并且不会在那里进行测试 – Marco13

您不需要帐户即可测试您的代码。 https://codility.com/demo/train/ – stepler

要理解为什么数字“2”以下结果[2,4,3,2,0]出现两次见下文

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

来源

2014-01-23 20:42:52

代码，因为返回数字代表非除数的数量！对于索引[0]，有2个非分割者，对于索引[3]，也有2个非分割者。

来源

2014-01-24 11:03:53 user3157761

-1

/** 
* Count Non-divisible 
*/ 

public class Solution { 

    public int[] solution(int[] A) { 
     int[] div = new int[A.length]; 
     for (int e = 0; e < div.length; e++) { 
      div[e] = 0; 
      for (int i = 0; i < A.length; i++) { 
       int dividend = A[e]; 
       if (dividend % A[i] != 0) { 
        div[e] += 1; 
       } 
      } 
     } 
     return div; 
    } 

    public static void main(String args[]) { 
     int[] A = new int[]{3, 1, 2, 3, 6}; 
     Solution s = new Solution(); 
     int[] B = s.solution(A); 
     for (int i = 0; i < B.length; i++) { 
      System.out.println(B[i]); 
     } 
    } 
}

来源

2014-01-25 15:17:01 furqan

解决方案的复杂性是n^2。 Codility需要n * log（n）。 – stepler

此解决方案提供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; 
}

谢谢大家的帮助。

来源

2014-01-27 20:08:28 stepler

这算法上与我的解决方案不同吗？（如果没有，我至少可以说我的解决方案是为了理解方法，为了获得高分; - ））。如果它不同（除了像sqrt优化这样的小事情），这种差异的解释会很好。 – Marco13

@Marco区别是除数搜索，我不存储所有的因数集，只计算除数。总的来说，我对你的解决方案有了基本的想法。我说它帮助了我。谢谢。 – stepler

这是我的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

来源

2014-01-28 05:15:10 Sheng

我想我会分享我的解决方案在C++中获得100分。我认为这很简单。

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

首先它计数阵列中的每个号码的出现。
然后，对于每个数组元素i，它找到在1到sqrt(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; 
}

来源

2014-02-20 18:51:38 jaho

看起来这个解决方案的复杂性是'O（N * sqrt（N））'。外循环 - “N”迭代，内循环 - 达到sqrt（2 * N）迭代。 –

这个工作对我有100％的得分基于C

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

来源

2015-05-04 17:04:13 Roman

100％的JavaScript。 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; 
}

来源

2015-08-29 12:37:39 mcm

而不是'parseInt（num/x）=== num/x'你可以做'num％x === 0' –

在这里，我们一起去我就得到了100％的解决方案：

boolean[] result_; 
public int[] solution(int[] A) { 
int a[][] = new int[2*A.length + 1][2]; 
result_ = new boolean[2*A.length + 1]; 
for(int i : A) { 
    ++a[i][0]; 
} 
a[1][1] = A.length - a[1][0]; 
result_[1] = true; 
for(int i : A) { 
    multCount(a,A,i); 
} 
int[] result = new int[A.length]; 
for(int i=0;i<result.length; i++) { 
    result[i] = a[A[i]][1]; 
} 
return result; 

} 

private void multCount(int[][] a, int[] A, int item) { 
if(result_[item]) 
    return; 
int sub=(int)Math.sqrt(item); 
    a[item][1] = A.length; 
if(item % sub == 0&& sub >1){ 

    a[item][1] -= a[sub][0]; 
    int rest = item/sub; 
    if(rest != sub) { 

     a[item][1] -= a[rest][0]; 
    } 
} 

a[item][1] -= a[item][0]; 
a[item][1] -= a[1][0]; 
for(int i=2; i<sub; i++) { 
    if(item % i == 0) { 
     a[item][1] -= a[i][0]; 

     int rest = item/i; 

     a[item][1] -= a[rest][0]; 

    } 
} 
result_[item] = true; 
    }

https://codility.com/demo/results/trainingZ2VRTK-5Y9/

来源

2015-10-11 14:14:42

你能解释一下你的代码，所以你的答案对别人更有用吗？ – wmk

所有的数字都在1和2之间* N –

所有的数字都在1和2之间* N 我们创建了一个有两个角的数组数组的索引是数字本身第二个维是一个数组，它有两个数字第一个是数第二个是第一个数字是由该阵列，用于直接填充答案的计数（INT I：A）{ ++ A [1] [0]; } 例如：假设阵列A具有以下项目： [1,3,1,5,3] 的二维阵列将被填充作为随后 {{0,0}，{2,0} ，{0,0}，{2,0}，{0,0}，{1,0}，{0，}，..} 含义：数字0有0计数数字1有2计数 2号有0计数 3号有两个计数 –

这是我在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; 
}

来源

2015-11-06 14:42:53 Mario

// C++ 100％，分解到素数，并检查所有可能的除数。 //我想知道，它的真实时间是多么的复杂。

包括

空隙make_factorization_array（INT N，性病::矢量&筛） {

for(int i = 2;i*i <= N;i++) 
{ 
    if(sieve[i] == 0) 
    { 
     int k = i*i; 
     for(int j = k;j <= N;j += i) 
     { 
      auto& e = sieve[j]; 
      if(e == 0) 
       e = i; 
     } 

    } 

}

}

INT count_divisors（标准::矢量&除数，性病::矢量> &素数，int prime_index，int初始值） {

auto& p = primes[prime_index]; 

int c = 0; 

int v = initial; 

int max = p.second; 

if(p.first == 1) 
    max = 0; 

for(int i = 0;i <= max;i++) 
{     

    if(prime_index != primes.size() - 1) 
     c += count_divisors(divisors, primes, prime_index + 1, v); 
    else 
     c += divisors[v]; 

    v = v * p.first; 

} 

return c;

}

载体溶液（矢量& A）{// 用C++ 11（克++ 4.8.2）代码

int me = *std::max_element(A.begin(), A.end()); 

std::vector<int> factorization_array; 
std::vector<int> sieve(me + 1, 0); 
make_factorization_array(me, sieve);  

std::vector<int> divisors(me + 1, 0);   
for(auto i = A.begin();i != A.end();i++) 
    divisors[*i]++; 

vector<int> r; 
r.reserve(A.size()); 

for(auto i = A.begin();i != A.end();i++){ 


    std::vector<std::pair<int, int> > primes; 
    primes.reserve(*i); 

    int k = *i; 

    int last_prime = 0; 
    int power = 0; 

    while(sieve[k] > 0) 
    { 
     if(last_prime != sieve[k]) 
     { 
      if(last_prime != 0) 
       primes.push_back(std::make_pair(last_prime, power)); 
      power = 1; 
      last_prime = sieve[k]; 
     } else 
     { 
      power++; 
     }     
     k = k/sieve[k];       
    } 

    if(last_prime == k) 
     primes.push_back(std::make_pair(last_prime, power + 1)); 
    else 
    { 
     if(last_prime != 0) 
      primes.push_back(std::make_pair(last_prime, power)); 
     primes.push_back(std::make_pair(k, 1)); 
    }         

    int c = count_divisors(divisors, primes, 0, 1);    

    r.push_back(A.size() - c); 
} 
return r;

}

来源

2016-04-23 08:29:51

我使用的hashmap，它满足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; 
    } 
}

来源

2017-01-29 17:23:37 Soley

CountNonDivisible - Codility培训任务

回答

相关问题