0

試験の質問はこれです：

リストでの一般的な操作は、リスト内の「最大」の値を見つけることです。リスト内で「2番目に大きい」値を見つけるアルゴリズムを記述します。リストには少なくとも2つの値が含まれ、値が重複していないと想定できます。答えとしてC＃コードを記述しないでください。ただし、アルゴリズムは、C＃またはその他のプログラミング言語での実装に役立つ詳細レベルである必要があります。

アルゴリズムは、提供されている機能、たとえば、SortなどのC＃配列クラスメソッドを使用しないでください。このアルゴリズムは、リストの2番目に大きい値の場所を返すメソッドとして実装され、その順序も想定されます。リスト内の値の一部は変更されていません。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)これは、最大の要素を見つけるのと同じ方法で実行できます。見つかった最大の要素と 2 番目に大きい要素の 2 つの変数を保持するだけです。リストを反復処理するときに、これら 2 つの変数を更新する方法を考えてください。

于 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 に答える