擅长:python、mysql、java
<p>对于一般的未排序数组,您永远无法在小于O(n)的时间内找到<code>max</code>。一个非常简单的证明:如果在不到O(n)的时间内完成,那么对于一个足够大的数组,就没有足够的时间检查每个元素。因此,对手可以将最大值放在您不检查的元素中,从而使您的算法不正确。在</p>
<p>原始代码的优点是使用少于2n的比较同时找到<em>最大值和最小值(就像朴素的实现一样),它使用大约1.5n的比较,因为当有两个元素时它只执行一个比较。使用它只找到最大值不会带来任何好处:最好在Python中使用<code>max(arr)</code>(这也会更快,因为它没有函数调用开销)。在</p>
<p>原始代码将值存储在<code>a[1]</code>到<code>a[n]</code>中,这需要一个大小为<code>n+1</code>的数组。因此,您应该在第一个位置放置一个虚拟元素。在</p>
<p>但是,更麻烦的是,你的翻译是不正确的。原始版本使用全局变量来实现多值返回(这是一种非常老练的方法),并使用局部变量来保存旧的全局变量。由于您使<code>max1</code>和<code>max2</code>都是全局的,所以该函数无论如何都不会产生正确的答案。在</p>
<p>正确的Python转换将使用带有元组的直接多值返回:</p>
<pre><code>def minmax(arr, i, j):
if i==j:
return arr[i], arr[i]
elif i==j-1:
if arr[i] < arr[j]:
return arr[i], arr[j]
else:
return arr[j], arr[i]
else:
mid = (i+j)//2
min1, max1 = minmax(arr, i, mid)
min2, max2 = minmax(arr, mid+1, j)
if min2 < min1: min1 = min2
if max2 > max1: max1 = max2
return min1, max1
</code></pre>