要求您在A [关闭]中找到第二个最大数字

Question

关闭。这个问题需要更多focused。它当前不接受答案。

---

是否要改善此问题？更新问题，使其仅按editing this post专注于一个问题。

关闭7分钟前。

给出n => 2个正整数的数组A，要求您找到第二个A中的最大数字。

1. 设计分治算法以解决该问题。
2. 证明您的算法正确。
3. 找出算法的时间复杂度。（为简单起见，您可以假设n为2的幂。）

Answer 1

int biggest = -99999999
int second  = -99999999

for i = 0 ... n-1
|   if A[i] >= biggest
|   |   second = biggest
|   |   biggest = A[i]
|   else if A[i] >= second
|   |   second = A[i]
return second

由于我们只查找数组的每个元素一次，所以复杂度为O（n）。