4

次の方法で配列をソートする必要がある演習があります。

  1. 4 を割った余りがない数が配列の最初になります (例: 4,8,12,16)。
  2. 4 を 1 で割った数は、配列の 2 番目 (1,5,9) になります。
  3. 4 を 2 で割った数は、配列の 3 番目 (2,6,10) になります。
  4. 4 を 3 で割る数は、配列の最後になります。

たとえば、次の配列です。

int []a={1,7,3,2,4,1,8,14}

になります：

4   8   1   1   2   14  3   7

グループ内の順序は重要ではありません。

O(n) の時間の複雑さと O(1) の空間の複雑さで機能するソリューションを見つけました。

しかし、それは醜く、配列上を 3 回移動します。よりエレガントなソリューションが必要です。

これは私のコードです: 

    int ptr=a.length-1; int temp=0, i=0;
    while (i<ptr){
        //move 3 remained to the end
        if (a[i] % 4==3){
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }
    i=0;
    while (i<ptr){
        if (a[i]%4==2)
        {
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }
    i=0;
    while (i<ptr){
        if (a[i]%4==1)
        {
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }

知っておくべき重要事項:

  • 時間の複雑さを O(n) よりも悪くしたくないし、空間の複雑さを O(1) よりも悪くしたくありません。
4

3 に答える 3

6

O(3 * N) は O(N) であるため、配列を 3 回ループするだけで済みます。

  1. 要素を前に移動しe % 4 == 0、途中で要素を入れ替えます。
  2. 要素を前に移動しe % 4 == 1、途中で要素を入れ替えます。
  3. 要素を前に移動しe % 4 == 2、途中で要素を入れ替えます。

e % 4 == 3この後最後にある要素。

例：

public static void main(String args[]) {
    int[] a = { 1, 7, 3, 2, 4, 1, 8, 14 , 9};
    int current = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = current; j < a.length; j++) {
            if (a[j] % 4 == i) {
                int b = a[j];
                a[j] = a[current];
                a[current] = b;
                current++;
            }
        }
    }
    System.out.println(Arrays.toString(a));
}
于 2013-06-28T15:59:49.977 に答える
1

より多くのメモリを使用できます。これは正しくありませんが、それでも入れます。

int modulusLength = 4;
List<Integer> array[] = new List<Integer>[modulusLength];
for(int i = 0; i < modulusLength; i++)
    array[i] = new ArrayList<Integer>;

for(int i = 0 ; i < a.length; i++)
    array[a[i]%modulusLength].put(a[i]);

int counter = 0;
for(int i = 0 ; i < array.length; i++)
    for(int j = 0; j < array[i].size; j++)
    {
        a[counter] = array[i].get(j);
        counter++;
    }

怖くて怖いけど、書いてて楽しかったです。そしてそれは動作します:)

于 2013-06-28T16:04:20.780 に答える