6

最近、C＃で質問に直面しました。質問は、次のとおりです。-3つのint配列があります。

Array1 = {88,65,09,888,87}

Array2 = {1,49,921,13,33}

Array2 = {22,44,66,88,110}

今、私はこれら3つの配列すべてから最高の5つの配列を取得する必要があります.c＃でこれを行うための最も最適化された方法は何ですか？

私が考えることができる方法は、サイズ15の配列を取得し、3つの配列すべての配列要素を追加して、最後の5を取得するように並べ替えることです。

4

7 に答える 7

2

固定のための最も最適化された方法は、K=5すべての配列を5回ゴングし、各パスでこれまでに取得されていない最も高い要素を選択することです。後続のパスで要素をスキップするには、取得する要素にマークを付ける必要があります。O(N1+N2+N3)これには、 （すべての要素を5回実行する）の複雑さがあり、N1+N2+N3可能な限り高速です。

于 2013-03-24T02:58:22.477 に答える
2

LINQを使用した簡単な方法：

int[] top5 = array1.Concat(array2).Concat(array3).OrderByDescending(i => i).Take(5).ToArray();

最適な方法：

 List<int> highests = new List<int>(); // Keep the current top 5 sorted
 // Traverse each array. No need to put them together in an int[][]..it's just for simplicity
 foreach (int[] array in new int[][] { array1, array2, array3 }) {
     foreach (int i in array) {
         int index = highests.BinarySearch(i); // where should i be?

         if (highests.Count < 5) { // if not 5 yet, add anyway
             if (index < 0) {
                highests.Insert(~index, i);
             } else { //add (duplicate)
                highests.Insert(index, i);
             }
         }
         else if (index < 0) { // not in top-5 yet, add
             highests.Insert(~index, i);
             highests.RemoveAt(0);
         } else if (index > 0) { // already in top-5, add (duplicate)
             highests.Insert(index, i);
             highests.RemoveAt(0);
         }
     }
 }

トップ5のソートされたリストを保持し、各配列を1回だけトラバースします。

BinarySearchを避けて、毎回トップ5の最低をチェックすることもできます。

 List<int> highests = new List<int>();
 foreach (int[] array in new int[][] { array1, array2, array3 }) {
     foreach (int i in array) {
         int index = highests.BinarySearch(i);
         if (highests.Count < 5) { // if not 5 yet, add anyway
             if (index < 0) {                    
                highests.Insert(~index, i);
             } else { //add (duplicate)
                highests.Insert(index, i);
             }
         } else if (highests.First() < i) { // if larger than lowest top-5                
             if (index < 0) { // not in top-5 yet, add
                highests.Insert(~index, i);
                highests.RemoveAt(0);
             } else { // already in top-5, add (duplicate)
                highests.Insert(index, i);
                highests.RemoveAt(0);
             }
         }
     }
}
于 2013-03-24T03:06:49.177 に答える
1

LINQを使用して配列を結合し、並べ替えてから、逆にすることができます。

    int[] a1 = new int[] { 1, 10, 2, 9 };
    int[] a2 = new int[] { 3, 8, 4, 7 };
    int[] a3 = new int[] { 2, 9, 8, 4 };

    int[] a4 = a1.Concat(a2).Concat(a3).ToArray();

    Array.Sort(a4);
    Array.Reverse(a4);

    for (int i = 0; i < 5; i++)
    {
        Console.WriteLine(a4[i].ToString());
    }
    Console.ReadLine();

印刷：配列の入力として提供したサンプルからの10、9、9、8、8。

于 2013-03-24T03:05:57.740 に答える
0

たぶん、「最大値」配列となる5つの要素の配列を持つことができます。

最初に最初の5つの値を入力します。この場合は、最初の配列になります。次に、残りの値をループします。各値について、最小から最大までの5つの最大値と照合します。メインリストの現在の値がmaxvalues配列の値より大きい場合は、配列内のその要素の上に挿入します。これにより、最後の要素が押し出されます。最後に、5つの最大値の配列が必要です。

于 2013-03-24T02:57:29.990 に答える
0

長さN1、N2、N3の3つの配列の場合、最速の方法は3つの配列を組み合わせてから、修正されたクイックソートを使用して（N1 + N2 + N3-4）次数の統計を見つけることです。

結果の配列では、インデックス（N1 + N2 + N3-5）から最大値（N1 + N2 + N3-1）までの要素が最大の5つになります。後で並べ替えることもできます。

このアプローチの時間計算量は、平均してO（N1 + N2 + N3）です。

于 2013-03-24T06:17:31.207 に答える
0

このタスクを実行する2つの方法があります。1つ目は、基本タイプのみを使用しています。これは最も効率的な方法であり、余分なループ、余分な比較、余分なメモリ消費はありません。別の要素と一致させる必要のある要素のインデックスを渡し、指定された配列ごとに次に一致するインデックスを計算するだけです。

最初の方法-

http://www.dotnetbull.com/2013/09/find-max-top-5-number-from-3-sorted-array.html

ここに画像の説明を入力してください

2番目の方法-

int[] Array1 = { 09, 65, 87, 89, 888 };
int[] Array2 = { 1, 13, 33, 49, 921 };
int[] Array3 = { 22, 44, 66, 88, 110 };

int [] MergeArr = Array1.Concat(Array2).Concat(Array3).ToArray();
Array.Sort(MergeArr);
int [] Top5Number = MergeArr.Reverse().Take(5).ToArray()

から取られた-

与えられた3つのソートされた配列から最大上位5つの数を見つけます

于 2013-09-16T07:23:47.170 に答える
0

簡単な答え： .NETのソートされたコレクションタイプのSortedListを最小ヒープとして使用します。

説明：

  1. 最初の配列から、このSortedList/min-heapに5つの要素を追加します。
  2. 次に、配列の残りのすべての要素を繰り返し処理します。
    • 配列要素が最小ヒープ内の最小要素よりも大きい場合は、最小要素を削除して、この配列要素をヒープ内にプッシュします。
    • それ以外の場合は、次の配列要素に進みます。
  3. 結局、最小ヒープには、すべての配列の中で最大の5つの要素があります。

複雑さ： k個の要素のSortedListがある場合、最小値を見つけるのにLogk時間がかかります。この「最小値の検索」操作を何度も実行するため、これにすべての配列の要素の合計を掛けます。

O（n * Log k）の全体的な複雑さをもたらします。ここで、nはすべての配列の要素の総数であり、kは必要な最大数の数です。

于 2016-06-30T19:42:16.360 に答える