我试图用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)
非常感谢你!在
编辑
我会避免破坏挑战。。。因为我没有在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
相同的数字,但可以使用set
,max
(两次!)、min
和index
函数在array
上。这些功能相当昂贵。迭代次数取决于array
。在假设数组按相反的顺序排序:}。。。得到:
[22, 14, 6, 2]
。您可以将22
替换为22-14
,14
替换为{[8, 12, 4, 2]
。再次排序:[12, 8, 4, 2]
,再次替换:[4, 4, 4, 2]
。又一次,{cd47}换一次。实际上,在第一个过程中,14
可以被14-2*6 = 2
代替(就像在经典的GCD计算中一样),给出以下序列:收敛速度很快。在
^{pr2}$基准:
输出:
相关问题 更多 >
编程相关推荐