列表中第二大值的算法考试示例

Question

试题是这样的:

A common operation on a list is to find the “largest” value in a list. Write an algorithm which will find the “second largest” value in a list. You can assume that the list will contain at least 2 values and that no value is duplicated. Do not write C# code as your answer, but the algorithm should be at a level of detail that would lend itself to implementation in C# or any other programming language.

The algorithm should not make use of any supplied functionality, e.g. C# Array class methods such as Sort etc. It is also assumed that this algorithm would be implemented as a method which returns the location of the second largest value of the list and that the order of the values within the list is unchanged. This means that one cannot simply sort the array in ascending order and return (list.Length-2) as it is assume that the list will be passed by reference to this method.

我的回答是:

1)  define integer variables as i and j
2)  assume listValues is the list of values
3)  create a new list called values which is equal to listValues
4)  create a new list called largest
5)  i is equal to 0, j is equal to list length of “values” list
6)  a while loop which is:
    a)  while 1 <  j
    b)  if values[0] > values[j-1]:
        1)  new integer k, k = 0
        2)  while k < j - 1
            a)largest = largest + values[k]
            b)k = k + 1
        3)  values = largest
        4)  largest = empty list
    c) else: 
        1)  new integer l, l = j – 1
        2)  while l > 0
            a) largest = largest + values[l] 
            b) l = l – 1
        3)  values = largest
        4)  largest = empty list
7)  a while loop which is :
    a)  while i < j
    b)  if values[0] not equal to listValues[i]
        1)  largest = largest + listValues[i]
    c)  i = i + 1
8)  listValues = largest
9)  values = listValues
10)  largest = empty 
11) a while loop which is:
    a)  while 1 <  j
    b)  if values[0] > values[j-1]:
        1)  new integer k, k = 0
        2)  while k < j - 1
            a)  largest = largest + values[k]
            b)  k = k + 1
        3)  values = largest
        4)  largest = empty list
    c) else: 
        1)  new integer l, l = j – 1
        2)  while l > 0
            a)  largest = largest + values[l] 
            b)  l = l – 1
        3)  values = largest
        4)  largest = empty list
12)  return values[0]

我知道这是低效的，我可以在 6 和 9 之间的循环之外添加另一个循环，但考虑到我的考试将是基于纸质的，因此很难编辑，所以我这样做了。但我担心的是这个答案是否正确。如果有人检查，我会很高兴。

Answer 1

这可以在 O(n) 中完成，就像查找最大元素一样。只需保留两个变量——找到的最大元素和找到的第二大元素。想想当你遍历列表时如何更新这两个变量。