-2

[1,2,1,3,4,2,1,3,2,3,1,4,1,2,1,3,4,2,1,3,2,3,1,4,1,2,1,3,4,2,1,3,2,3,1,4,1,2,1,3,4,1,2,1,3,4,1,3,2,3,1,4,1,2,1,3,4,1,2,1,3,4,1,3,2,3,1,4,などの整数配列で[1-4]という要素の範囲を持つソリューションを探しています。 2] このように、コア Java で最小限の時間の複雑さで並べ替える必要があります。

誰かが最小限の時間の複雑さでこれを解決するのを手伝ってくれますか?

4

5 に答える 5

3

1、2、3、4 の数を数え、その数に応じて数字を元に戻します。

int[] count = new int[5]; // 0..4
for (int a : data) {
    data[a]++;
}
int p = 0;
for (int i = 0 ; i != count.length ; i++) {
    for (int j = 0; j != count[i] ; j++) {
        data[p++] = i;
    }
}

最も内側の代入が実行される回数は、元の配列内の項目の数と正確に等しいため、2 つの入れ子になったループがあるにもかかわらず、線形時間の複雑さがあります。

于 2013-07-28T11:26:34.193 に答える
1

入力を 1 回スキャンし、配列にカウントして、再度展開することができます。私が知る限り、これはn+m複雑さを与えるでしょう。nは配列mの長さであり、 は範囲の長さです。配列の代わりに順序付けられた O(1) ハッシュを使用すると、O(n) に近づけることができる場合があります。

    int range_min = 1, range_max = 4;

    int[] input        = {1, 2, 1, 3, 4, 2, 1, 3, 2, 3, 1, 4, 2};
    int[] output       = new int[input.length];
    int[] intermediate = new int[range_max-range_min+1];

    for(int num : input)                        
        intermediate[num-range_min]++;

    int cnt = 0;
    for(int i=0; i<range_max-range_min+1; i++)  
        for(int j=0; j<intermediate[i]; j++)
            output[cnt++] = i+range_min;
于 2013-07-28T11:34:03.660 に答える
0

Javaで直接利用できるソリューションであるため、おそらくArrays.sort(...)時間の複雑さは最小限になります。さらに、クイックソート (平均複雑度 O(n lg n)) に基づいているため、高い確率で最適なソリューションになる可能性があります。

于 2013-07-28T11:14:53.313 に答える
0

k が「小さい範囲」の場合、カウント ソートが最も適しています。線形 (O(n+k)) の複雑さがあります。

于 2013-07-28T11:23:30.530 に答える
0

整数のみを並べ替える場合は、Arrays.sort() (Quicksort) がおそらく最善の方法です。通常、私は独自の並べ替えインターフェイスを作成するため、compareTo(Obj,Obj) を使用してインターフェイスを設定できます。 2. Obj を引数として、異なるカテゴリでソートします。たとえば、ビューで並べ替える場合は 1 を渡し、いいねで並べ替える場合は 2 を渡します。

ソートするデータが多く (デフラグなど)、実行可能な RAM よりも多くの RAM を消費する可能性がある場合は、マージソートを使用します。これは、RAM にすべてのデータをソートする必要がないためです。

于 2013-07-28T11:33:07.303 に答える