Линейное решение
Наиболее асимптотически эффективный способ сделать это - использовать сортировку сегментов .
- У вас есть 4 сегмента, одиндля каждого из классов конгруэнтности чисел по модулю 4.
- Сканирование чисел в массиве один раз
- Поместить каждое число в правильное ведро
- Тогдапостроить выходной массив
- Сначала поставить все числа из сегмента 0, затем все из сегмента 1, затем сегмента 2, затем сегмента 3
Таким образом, это сортируетчисла в O(N), что является оптимальным.Ключевым моментом здесь является то, что сортировка по числам по модулю 4 позволяет отсортировать только 4 числа: 0, 1, 2, 3.
Иллюстративное решение с List
Вот реализация вышеупомянутого алгоритма (для общего по модулю M), использующего List и для каждого для ясности.Не обращайте внимания на непроверенное предупреждение о приведении, просто сконцентрируйтесь на понимании алгоритма.
import java.util.*;
public class BucketModulo {
public static void main(String[] args) {
final int M = 4;
List<Integer> nums = Arrays.asList(13,7,42,1,6,8,1,4,9,12,11,5);
List<Integer>[] buckets = (List<Integer>[]) new List[M];
for (int i = 0; i < M; i++) {
buckets[i] = new ArrayList<Integer>();
}
for (int num : nums) {
buckets[num % M].add(num);
}
nums = new ArrayList<Integer>();
for (List<Integer> bucket : buckets) {
nums.addAll(bucket);
}
System.out.println(nums);
// prints "[8, 4, 12, 13, 1, 1, 9, 5, 42, 6, 7, 11]"
}
}
Как только вы полностью поймете алгоритм, перевод его для использования массивов (если необходимо) будет тривиальным.
Специальное примечание по %
Условие, что числанеотрицательный является существенным, потому что % НЕ является оператором по модулю , поскольку он математически определен;это оператор Остаток .
System.out.println(-1 % 2); // prints "-1"
Ссылки