对于Codility中的问题CountNonDivisible，我的逻辑有什么问题？
对于Codility中的问题CountNonDivisible，我的逻辑有什么问题？
提问于 2021-01-17 00:28:14
我正在尝试解决CountNonDivisible在代码上的问题，下面是我的解决方案。我的总分只有55%。我的逻辑是计算数组中存在的元素的所有除数，并从数组的总长度中减去它们，以获得每个元素的非除数的数量。
此问题来自Codility的lessons部分，可以在Lesson 11：CountNonDvisible下的链接中查看
import math
def solution(A):
B = reversed(sorted(A))
d = dict()
n = len(A)
res = dict()
for i in A:
if i not in d:
d[i] = 1
continue
d[i]+= 1
for i in B:
tmp = 0
if i == 1:
res[i] = n-d[i]
continue
if i==2 or i==3:
res[i] = n-d[i]-d.get(1,0)
continue
for j in range(2,int(math.sqrt(i)+1)):
if j in d and i%j == 0:
if j == i//j:
tmp+=d[j]
else:
tmp+=d[j]+d.get(i//j,0)
if d[i]>1:
res[i] = n-tmp-d.get(1,0)-d.get(i)
else:
res[i] = n-tmp-d.get(1,0)-1
ans = []
for i in A:
ans.append(res[i])
return ans回答 1
Stack Overflow用户
发布于 2021-01-17 01:46:32
首先，让我们编写一个简单的函数，它可以正确地解决问题，尽管效率可能很低：
def basic_sol(B):
return [ len([d for d in B if b % d != 0]) for b in B ]然后让我们运行一个测试，看看我们是否可以找到一些错误案例：
TRIALS=100
LENGTH=2
MAX_NUM=100
for trial in range(TRIALS):
B = [ random.randint(1, MAX_NUM) for j in range(LENGTH) ]
my_sol = solution(B)
correct_sol = basic_sol(B)
if(my_sol != correct_sol):
print(B)
print(my_sol)
print(correct_sol)
break这很快就会产生一些结果：
Problem [63, 21]
My solution [1, 1]
Correct solution [0, 1]由于63既可以被自身整除，也可以被21整除，因此列表中未除以它的项数应该为零，但您的程序返回1。
现在，您的工作是获取此测试用例，在您的程序中运行它，并找出它被错误处理的原因。
另外，问问你自己，你的解决方案比给出的单行解决方案到底有多有效。看起来两者都是O(n^2)。也许这里有一种更有效的方法来处理事情？
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65751835
复制相关文章
相似问题
腾讯云开发者
