第二最高元素

-2

要查找数组的第二个最高元素，是排序整个数组（排序），然后打印排序数组的第二个最高元素，或者应该找到数组的最高元素，删除它并再次找到最高元素（这将是第二高元素）？第二最高元素

来源

2016-06-26 floralmural

第一个选项是更好的。使用'Array.sort'并打印第二个元素。也请提供必要的细节。 – Rajesh

找到最高的，然后是第二高的更好。因为它与'nlog（n）'的合并排序（或通常使用的快速排序）相比只是'O（n）'。 –

你可以参考下面的帖子http://stackoverflow.com/questions/2615712/finding-the-second-highest-number-in-array – Rajesh

坦率地说，排序数组最好是O（nlog（n））操作（不要使用冒泡排序，顺便说一下）。遍历数组两次仍然是一个O（n）操作，但是您可以节约大约一半的运行时间 - 您可以一次遍历数组并存储次数最多的数据。

考虑以下（在Java中给出了一个int阵列的例子，但应该很容易平移以任何其它语言或数据类型）：

int secondHighest(int[] arr) { 
    // Assumption: There are at least two elements in the array 
    int highest; 
    int secondHighest; 
    if (arr[0] > arr[1]) { 
     highest = arr[0]; 
     secondHighest = arr[1]; 
    } else { 
     highest = arr[1]; 
     secondHighest = arr[0]; 
    } 

    for (int i = 2; i < arr.length; ++i) { 
     if (arr[i] >= highest) { 
       secondHighest = highest; 
       highest = arr[i]; 
      } else if (arr[i] > secondHighest) { 
       secondHighest = arr[i]; 
      } 
    } 

    return secondHighest; 
}

来源

2016-06-26 04:43:10 Mureinik

您应该单程遍历数组，跟踪最上面的两个元素。

来源

2016-06-26 04:38:23

这将是一个好主意，陈述为什么这更好，其他则只是说明。 –

我认为一个新手不是大O或内存带宽的家庭，但可以：排序通常是O（N log N），冒泡排序是O（N^2），并且一旦降低常数因子通过它两次运行，并更容易缓存。 –

如果他们不这样做，你可以简单地说这种方式更有效率，因为它只是通过数组迭代一次/（两次），而排序将遍历数组多次。我之所以在思考，是因为他们知道他们之前可能看到过什么是泡沫。 –

它是在一次通过完全可能的，并且更有效的方式。你寻找最高的两个值，然后选择第二个值。

伪代码

INTEGER FINDSECONDHIGHEST (ARRAY A) 
    INTEGER FIRST = MINIMUM_INTEGER_VALUE_POSSIBLE 
    INTEGER SECOND = MINIMUM_INTEGER_VALUE_POSSIBLE 

    FOREACH INTEGER I IN A 

     IF I > FIRST THEN 

      SECOND = FIRST 
      FIRST = I 

     ELSE IF I > SECOND THEN 

      SECOND = I 

     END IF 

    END FOREACH 

RETURN SECOND

来源

2016-06-26 07:33:27

第二最高元素

回答

相关问题