遍历数组以找到线性时间中的第二大元素

Question

有没有一种方法可以在线性时间内找到哪个是数组的第二大元素？数组元素可以是正数,负数或零.元素可以重复.没有STL允许.可以使用Python.

解决方案:对数组进行排序并获取第二个元素,但不允许排序

修改:根据定义,第二大元素将是数值较小的元素.就像我们有

Arr = {5,5,4,3,1}然后第二大是4

添加 让我们说如果我想将问题概括为kth最大且复杂度小于线性,如nlogn,那么解决方案是什么呢？

Answer 1

浏览数组,保留2个内存插槽,记录到目前为止看到的2个最大元素.返回两者中较小的一个.

....对于这个我看不到的问题,有什么棘手的问题吗？

Answer 2

你可以,这是伪算法:

max = 2max = SMALLEST_INT_VALUE;

for element in v:
   if element > max:
      2max = max;
      max = element;

  else if element > 2max:
      2max = element;

2max是您正在寻找的价值.

对于特定情况,算法不会返回正确的值,例如其元素相等的数组.