Отсортировать массив по оставшейся части 4

Question

У меня есть упражнение, в котором я должен сортировать массив следующим образом:

1. числа, которые делят 4 без остатка будет первым в массиве (например, 4,8,12,16).
2. номера, которые делят 4 с остатком 1, будут вторыми в массиве (1,5,9).
3. числа, которые делят 4 с остатком 2, будут третьим в массиве (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).

Answer 1

Так как O (3 * N) является O (N), вам нужно только петли через массив три раза:

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)); 
} 

Answer 2

Вы можете использовать больше памяти. Это неверно, но я все равно его положу.

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++; 
    } 

Ужасно и страшно, но было интересно писать. И это работает :)

Answer 3

Просто используйте компаратор и используйте для очень эффективного внутреннего алгоритма сортировки.

Arrays.sort(a, new Comparator() { 
public int compare(int a, int b) { 
    if(a%4 == b%4) { 
    if(a < b) return -1; 
    if(a > b) return 1; 
    return 0; 
    } else { 
    if(a%4 < b%4) return -1; 
    if(a%4 > b%4) return 1; 
    return 0; 
    } 
} 
});