尝试优化此代码:迭代列表以替换其值

2024-03-29 12:28:10 发布

您现在位置:Python中文网/ 问答频道 /正文

我试图用Python进行挑战,挑战包括: 给定一个X为正整数的数组,其元素将通过在其上运行以下操作进行转换(根据需要多次执行):

如果X[i]>;X[j],则X[i]=X[i]-X[j]

当无法再进行转换时,返回其和(“最小可能和”)。在

基本上,您从数组中选择两个不相等的数字,并用减法替换其中最大的一个。重复这个步骤,直到数组中的所有数字都相同。在

我尝试了一个基本的方法,使用最小值和最大值,但还有另一个约束,那就是时间。我总是超时,因为我的代码没有经过优化,执行时间太长。你能提出一些解决办法使它运行得更快吗。在

def solution(array):
    while len(set(array)) != 1:
        array[array.index(max(array))] = max(array) - min(array)
    return sum(array)

非常感谢你!在


Tags: 方法代码gt元素def时间步骤数字
1条回答
网友
1楼 · 发布于 2024-03-29 12:28:10

编辑

我会避免破坏挑战。。。因为我没有在Python中找到解决方案。但这是一个在Kotlin(538ms)中工作的算法的总体设计。在Python中,我被困在性能测试的中间。在

一些想法:

  • 我们将尽可能地去掉最小的模,这是最好的。在
  • 其次,如果这个最小值是1,那么数组很快就会充满1,结果是N(数组的长度)。在
  • 第三,如果所有元素都相等,结果是N乘以一个元素的值。在

算法

其思想是保持两个索引:i是在0..N上循环的当前索引,k是当前最小值的索引。 开始时,k = i = 0,最小值为m = arr[0]。我们前进i,直到发生以下情况之一:

  • i == k=>;我们完成了一个完整的循环,没有更新k,返回{}
  • arr[i] == 1=>;返回N
  • arr[i] < m=>;更新k和{}
  • arr[i] > m=>;计算arr[i]的新值(即arr[i] % m或{},如果{}是{}的倍数)。如果不是m,那就是arr[i] % m < m:更新k和{}
  • arr[i] == m=>;通过。在

基本上,我们使用滚动最小值,动态计算模,直到所有元素都相同为止。这就避免了周期性地计算数组的min。在

上一个答案

正如@BallpointBen所写,您将得到所有数字的n倍的GCD。但那是欺骗;)!如果你想手工找到解决方案,你可以优化你的代码。在

虽然找不到N相同的数字,但可以使用setmax(两次!)、minindex函数在array上。这些功能相当昂贵。迭代次数取决于array。在

假设数组按相反的顺序排序:[22, 14, 6, 2]。您可以将22替换为22-1414替换为{}。。。得到:[8, 12, 4, 2]。再次排序:[12, 8, 4, 2],再次替换:[4, 4, 4, 2]。又一次,{cd47}换一次。实际上,在第一个过程中,14可以被14-2*6 = 2代替(就像在经典的GCD计算中一样),给出以下序列:

[22, 14, 6, 2]
[8, 2, 2, 2]
[2, 2, 2, 2]

收敛速度很快。在

^{pr2}$

基准:

import random
import timeit

arr = [4*random.randint(1, 100000) for _ in range(100)] # GCD will be 4 or a multiple of 4

assert solution(list(arr)) == solution2(list(arr))

print(timeit.timeit(lambda: solution(list(arr)), number=100))
print(timeit.timeit(lambda: solution2(list(arr)), number=100))

输出:

2.5396839629975148
0.029025810996245127

相关问题 更多 >