Сразу предупреждаю, что данная статья будет альтернативной версией вот этой. Да, я уж прям чую как все сразу ринуться меня критиковать, но, ребята, алгоритм представлений в решении не оптимален. В комментариях предлагали еще более простые алгоритмы, на питоне. На питоне достаточно написать:
И все. Кому нужен вообще какой-то алгоритм. В задании было установлено ограничение от 0 до 100, мы же не лентяи, сделаем в общем виде, для любых значений и с повторениями чисел. Немного подумав, пришел вот к такому решению:
А теперь, разберем что я тут написал.
В общем-то, проблема состоит в нахождение минимума и максимума, так как сравнение мы не можем использовать, то:
Если B по модулю будет больше чем А, то цикл попросту не выполнится и пойдет на возврат. Это довольно простое решение. Без «великих» математических формул. Просто и понятно. И еще: почему я беру по модулю? Это вызвано методом сортировки, который я использую.
В оригинальной статье используется сортировка «с флажком» (если я правильно понял). Выполнение такой сортировки при самом плохом случае О(N^2) (или близко к этому), что не есть хорошо.
Этот метод (не помню его название, искатьне царское это дело лень), решит за О(N) даже при том что числа будут повторяться.
Суть сортировки заключается в том что при заполнении массива он сам сортирует себя. Значение мы представляем в виде индекса и увеличиваем количество элементов в этом индексе.
Как оказалось (то ли я криворукий), массивы создаются от 0 до N и как я не старался сделать от -N до N, безуспешно. Поэтому делаем смещение, поэтому ищем максимум с модулем. Потом просто отражаем относительно 0 и получаем диапазон индексов в который точно влезут все элементы, кроме граничного, так что +1.
На этом у меня все. Поставленную задачу выполнил, при этом оптимизировав процесс и представив свое видение решения данной задачи.
array.sort()
И все. Кому нужен вообще какой-то алгоритм. В задании было установлено ограничение от 0 до 100, мы же не лентяи, сделаем в общем виде, для любых значений и с повторениями чисел. Немного подумав, пришел вот к такому решению:
Код
public class main {
public static int max(int a, int b) {
int i;
for (i = 0; i < a - Math.abs(b);) {
return a;
}
return Math.abs(b);
}
public static void main(String[] args) {
int[] arrayForSort;
int[] sortArray;
int NUM_ELEMENT = 20, maxNum = -1000, i, j;
arrayForSort = new int[NUM_ELEMENT];
for (i = 0; i < NUM_ELEMENT; i++) {
arrayForSort[i] = (int) (Math.random() * 101) - 50;
maxNum = max(maxNum, arrayForSort[i]);
System.out.print(arrayForSort[i] + " ");
}
System.out.println();
sortArray = new int[maxNum * 2 + 1];
for (i = 0; i < NUM_ELEMENT; i++) {
sortArray[arrayForSort[i] + maxNum]++;
}
for (i = 0; i <= maxNum * 2; i++) {
for (j = 0; j < sortArray[i]; j++) {
System.out.print(i - maxNum + " ");
}
}
}
}
А теперь, разберем что я тут написал.
В общем-то, проблема состоит в нахождение минимума и максимума, так как сравнение мы не можем использовать, то:
public static int max(int a, int b) {
int i;
for (i = 0; i < a - Math.abs(b);) {
return a;
}
return Math.abs(b);
}
Если B по модулю будет больше чем А, то цикл попросту не выполнится и пойдет на возврат. Это довольно простое решение. Без «великих» математических формул. Просто и понятно. И еще: почему я беру по модулю? Это вызвано методом сортировки, который я использую.
В оригинальной статье используется сортировка «с флажком» (если я правильно понял). Выполнение такой сортировки при самом плохом случае О(N^2) (или близко к этому), что не есть хорошо.
Этот метод (не помню его название, искать
for (i = 0; i < NUM_ELEMENT; i++) {
sortArray[arrayForSort[i] + maxNum]++;
}
Суть сортировки заключается в том что при заполнении массива он сам сортирует себя. Значение мы представляем в виде индекса и увеличиваем количество элементов в этом индексе.
Пример
Мы два раза встретили число 44, значит в отсортированном массиве по индексу 44 будет содержаться 2. Это просто!
Как оказалось (то ли я криворукий), массивы создаются от 0 до N и как я не старался сделать от -N до N, безуспешно. Поэтому делаем смещение, поэтому ищем максимум с модулем. Потом просто отражаем относительно 0 и получаем диапазон индексов в который точно влезут все элементы, кроме граничного, так что +1.
Пояснение
Мы получим минимум -48, а максимум 38. Так мы берем что минимум -48, а макс 48, для упрощение алгоритма. И смещаем так чтобы минимум был на 0 -48+48
sortArray = new int[maxNum * 2 + 1];
. . .
sortArray[arrayForSort[i] + maxNum]++;
. . .
System.out.print(i - maxNum + " ");
На этом у меня все. Поставленную задачу выполнил, при этом оптимизировав процесс и представив свое видение решения данной задачи.
Пример вывода
35 -29 26 17 -44 -10 31 -22 24 2 -28 17 2 -36 -30 35 39 -35 41 50
-44 -36 -35 -30 -29 -28 -22 -10 2 2 17 17 24 26 31 35 35 39 41 50
-44 -36 -35 -30 -29 -28 -22 -10 2 2 17 17 24 26 31 35 35 39 41 50
