0

サイズの異なる n 個の並べ替えられた配列があります。K i を与えるには、最初の k 個の最小数を見つける必要があります。
int a[] = {10,20,30,40};
int b[]= {20,30,40};
int c[] ={-10,0};

k = 1 の場合、出力は配列 = {-10}、k=2 の場合、op= {-10,0} k = 4 {-10,0,10,20,20} になります。

私が考えたアイデア:
1.最小ヒープを維持しますが、残りのすべての配列のすべての要素をスキャンする必要がありますか?
2.サイズKのop配列を維持し、配列「op」で最大値より大きい要素に遭遇しない限り、すべての配列のすべての要素をスキャンします

コラムから考え始める方法はありますか？

制約: すべての配列をマージして最初の k を見つけることは、配列のサイズが巨大になる可能性があり、1 つの配列に数百万の整数が含まれる場合があるため、適切ではありません。

4

4 に答える 4

1

基本的なマージ (マージ ソートなど) を使用すると、O(m) 時間 (m は要素の総数) で実行され、そこから最初の k 要素を選択することができます。

編集:マージに関する修正後:

別の解決策は、k 回反復し、各配列の最初の要素の最小値を見つけることです (つまり、配列 [1, 2, 3, 4, 5]、[2, 4, 6]、および [3 , 4, 7, 8], min(1, 2, 3). この最小値をソリューション配列 (k 個の最小整数) に追加し、それぞれの配列から削除します。

于 2013-01-18T23:11:11.950 に答える
1

これはあなたにアイデアを与えるかもしれません..

         List<int> new1 = new List<int>();
         List<int> testArr = new List<int>() { 10, 20, 30, 40 };
         List<int> testArr1 = new List<int>() { -10, 0 };
     int[] newArr=   testArr.Concat(testArr1).ToArray();

     var s1 = (from i in newArr
              orderby i ascending
              select i);
     foreach (var x in s1)
     {
         new1.Add(x);
     }
于 2013-01-18T23:22:35.443 に答える
0

一つの方法は

を使用してすべての並べ替えられた配列を単一の並べ替えられた配列に収束すると、答えは新しい配列の先頭から k 個の要素になります。これは、最初から各配列のインデックスを維持し、その配列の要素が結果配列にプッシュされたときにそれらをインクリメントすることで実行できます。これを 2 つのアレイに対して実行しましたが、同じものをさらに使用できます。

制約が追加された後の編集: すべての配列を調べ、長さ > k のものがあれば、長さ k に切り捨てます (それぞれが大きな配列である場合、これは適切なトレードオフになる可能性があります)。

// Find K largest numbers in two sorted arrays
//Returns 0 on success and -1 in failure and c contains the resulting array


int k_largest(a, b, c, k) {
    int a_len = a.length;
    int b_len = b.length;
    if (a_len + b_len < k) return -1;
    int i = 0;
    int j = 0;
    int m = 0;

if(a[k] < b[0])
c=a;
else if (b[k] < a[0])
c=b;

/* (i<k) test below is to discard the rest of the elements of the arrays ,
using the sorted property of array */

    while (i < k && j < a_len && m < b_len) {
        if (a[j] < b[m]) {
            c[i] = a[j];
            i++;
            j++;
        } else {
            c[i] = b[m];
            i++;
            m++;
        }
    }

    if (i === k) {
        return 0;
    } else if (j < a_len) {
        while (i < k) {
            c[i++] = b[m++];
        }
    } else {
        while (i < k) c[i++] = a[j++];
    }
    return 0;
}

a = 結果の配列と b = 3 番目の配列などを使用して、これをもう一度行います。

于 2013-01-18T23:10:22.577 に答える
0

別の方法は、配列をスタックのように使用することです。各配列で最後に使用された最小値へのポインターを保存し、各反復でそのすべてのポインター (例では 3 つのポインター) をチェックする必要があります。K 値を取得するには、K 回反復する必要があります。

以下は、c# のサンプル コードです。

 int[] a = new int[] {10,20,30,40};
 int[] b = new int[] {20,30,40};
 int[] c = new int[] {-10,0};

 Dictionary<object, int> dic = new Dictionary<object, int>();
 dic.Add(a, 0);
 dic.Add(b, 0);
 dic.Add(c, 0);

 int K = 4;

 for (int i = 0; i < K; i++)
 {
     var min = dic.Min(s => ((int[])s.Key)[s.Value]);
     var arr = dic.First(p => ((int[])p.Key)[p.Value] == min);
     int idx = arr.Value + 1;
     dic.Remove(arr.Key);
     if (((int[])arr.Key).Length > idx)
         dic.Add(arr.Key, idx);
     Console.WriteLine(min);
 }
于 2013-01-18T23:17:27.113 に答える