0

考试题是这样的：

对列表的常见操作是查找列表中的“最大”值。编写一个算法，它将在列表中找到“第二大”值。您可以假设该列表将包含至少 2 个值并且没有重复的值。不要将 C# 代码编写为您的答案，但算法的详细程度应适合用 C# 或任何其他编程语言实现。

该算法不应使用任何提供的功能，例如 C# Array 类方法，如 Sort 等。还假定该算法将被实现为返回列表第二大值的位置和顺序的方法列表中的值保持不变。这意味着不能简单地按升序对数组进行排序并返回 ( list.Length-2)，因为它假定列表将通过引用传递给该方法。

我这样回答：

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 之间的循环之外添加另一个循环，但考虑到我的考试将是基于纸质的，因此很难编辑，所以我这样做了。但我担心的是这个答案是否正确。如果有人检查，我会很高兴。

4

2 回答 2

3

这可以通过O(n)与查找最大元素相同的方式完成。只需保留两个变量 - 找到的最大元素和找到的第二大元素。考虑在遍历列表时如何更新这两个变量。

于 2012-06-02T14:57:49.033 回答
0

在 C 中

   int second_largest(int *arr, size_t len) {
      int i, j, k;
      assert(len > 1);
      k = (arr[0] > arr[1]) ? 0 : 1;
      i = arr[k];
      j = arr[1 - k];
      for (k = 2; k < len; k++)
      {
         if (arr[k] > i) { j = i;
                           i = arr[k]; }   
         else if (arr[k] > j) { j = arr[k]; }
      }
      return j;
   }
于 2012-06-02T17:20:53.110 回答