Codility每周一课：P11.1?CountNonDivisible

11.png

P11. 1 CountNonDivisible

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

P11. 1 非因子数
计算一个数组中所有元素的非因子数的个数

由N个整数组成的数组A。对于每个数A[i]，其中0≤i<N，要计算数组A中不是A[i]因子的元素数。并称这些元素为非因子数。

例如，整数N=5时的数组A：
A[0]=3，A[1]=1，A[2]=2，A[3]=3，A[4]=6

对于以下元素：
a[0]=3，非因子数为：2，6，个数为2；
a[1]=1，非因子数为：3，2，3，6，个数为4；
a[2]=2，非因子数为：3，3，6，个数为3；
a[3]=3，非因子数为：2，6，个数为2；
A[4]=6，没有任何非因子数，个数为0；

编写函数：

def solution(A)

给定一个由N个整数组成的数组A，则返回表示非因子数个数的序列。例如，针对上面的示例，函数应该返回[2，4，3，2，0]。

假定：

1. N是区间[1，50000]内的整数；
2. 数组A的每个元素都是区间[1，2*N]内的整数；

• 解题思路

首先得到数组A中各个元素出现的次数字典。而后遍历数组A，对于每一个元素j，在从1到sqrt(j)+1中寻觅j的因子，一次遍历可以取得2个(假如为平方根，则就只有一个)因子。假如因子在次数字典里，则加上其出现的次数。最后A的长度减去总的次数就可。并且要用字典存储已经取得非因子个数值的数，为了减少后面的重复的运算。

• Python3代码

# -*- coding：utf-8 -*-# &Author  AnFany# Lesson 11：Sieve of Eratosthenes# P 11.1 CountNonDivisibledef solution(A):    """    针对数组中的每一个元素，得到数组A中不是其因子数的个数, 时间复杂度O(N * log(N))    :param A: 数组A    :return: 返回每个元素的非因子数的个数序列    """    element_dict = {}    for i in A:        if i in element_dict:            element_dict[i] += 1        else:            element_dict[i] = 1     length = len(A)    no_divided = []    get_num = {}  # 用字典存储已经得到的非因子数个数，利用空间换时间    for j in A:        if j in get_num:            no_divided.append(get_num[j])        else:            count_j_factor = 0            for factor in range(1, int(j ** 0.5) + 1):                if j % factor == 0:                    if factor in element_dict:                        count_j_factor += element_dict[factor]                    other_factor = int(j / factor)                    if other_factor != factor and other_factor in element_dict:                        count_j_factor += element_dict[other_factor]            no_divided_count = length - count_j_factor  # 非因子数等于所有的个数减去因子占的总个数            no_divided.append(no_divided_count)              get_num[j] = no_divided_count    return no_divided

• 结果

image

点击取得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

imageimage