Сортировка строки с заглавными буквами и цифрами

Question

Сортировка строки с маленькими заглавными буквами и цифрами в Java aAbcB1C23.Ответ ABCabc123.

Я попытался отсортировать массив как по возрастанию, так и по убыванию, но не сработал, так как оба пути ABC идут посередине.Есть идеи ?

Я хотел бы решить с O (1) вспомогательным пространством и может быть O (n log n) времени ..

public class SortTheGivenStringAlphabetically {
    public static void performAction() {
        String input = "aAbcB1C23";
        char[] inputCharArray = input.toCharArray();
        sort(inputCharArray, 0, (inputCharArray.length) - 1);

        for (int i = 0; i < inputCharArray.length; i++) {
            System.out.println(inputCharArray[i]);
        }

    }

    public static void sort(char[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            sort(array, low, pi - 1);
            sort(array, pi + 1, high);
        }
    }

    private static int partition(char[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                char temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        char temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        performAction();
    }
}

Answer 1

Первый цикл повторяется не раз, когда число символов присутствует в String. И последние два цикла выполняются в течение постоянного времени (78 раз). Так что временная сложность может быть эффективной.

   public static String SortSstring(String input) {
        int []intArr=new int[78];
        for(int i=0;i<input.length();i++)
            intArr[input.charAt(i)-48] ++;
        String OutputString="";
        for(int i=17;i<78;i++){
            OutputString+=String.valueOf(new char[intArr[i]]).replace('\0', (char)(i+48));
        }
        for(int i=0;i<10;i++){
            OutputString+=String.valueOf(new char[intArr[i]]).replace('\0', (char)(i+48));
        }
        return OutputString;
    }
    }

Answer 2

Подлость в том, что естественный порядок равен '1' (49) < 'A' (65) < 'a' (97).

    String input = "aAbcB1C23"; // Sorted: ABCabc123
    char[] array = input.toCharArray();
    sort(array, 0, (array.length) - 1);

Так что вы можете изменить порядок неправильно отсортированных результатов:

output = output.replaceFirst("^([0-9]*)([A-z]*)$", "$2$1");

или отобразить каждый соответствующий символ направильное значение: проще всего с функцией:

int value(char ch) {
    if ('A' <= ch && ch <= 'Z') {
        return 100 + (ch - 'A');
    } else if ('a' <= ch && ch <= 'z') {
        return 200 + (ch - 'a');
    } else if ('0' <= ch && ch <= '9') {
        return 300 + (ch - '0');
    } else {
        return 400 + (int) ch;
    }
}

Теперь сравните value(array[i]).

Answer 3

Один из вариантов - использовать целочисленное значение символа при сравнении.Чтобы числа появились в конце, мы можем добавить к нему некоторое фиксированное значение (например, 100).

public static void main(String[] args) {
    String input = "aAbcB1C23";
    char[] charArray = input.toCharArray();
    Character[] charObjectArray = ArrayUtils.toObject(charArray);

    Arrays.sort(charObjectArray, new Comparator<Character>() {
        @Override
        public int compare(Character o1, Character o2) {
            Integer i1 = convert(Integer.valueOf(o1));
            Integer i2 = convert(Integer.valueOf(o2));
            return i1.compareTo(i2);
        }

        private Integer convert(Integer original) {
            if (original < 58) {
                return  original + 100;
            }
            return original;
        }
    });

    System.out.println(new String(ArrayUtils.toPrimitive(charObjectArray)));
}

Answer 4

• Создать 3 ArrayList с.
• Отделите все символы от ввода и добавьте их к определенному ArrayList.
• Затем отсортируйте их, используя Collections.sort().
• Наконец, объедините все символы в порядкеВы хотите.

---

String input = "aAbcB1C23";
ArrayList<Character> capital = new ArrayList(),
        simple = new ArrayList(),
        numbers = new ArrayList();

for (Character c : input.toCharArray()) {
    if (Character.isLetter(c)) {
        if (Character.isUpperCase(c)) {
            capital.add(c);
        } else {
            simple.add(c);
        }
    } else {
        numbers.add(c);
    }
}

Collections.sort(simple);
Collections.sort(capital);
Collections.sort(numbers);

StringBuilder output = new StringBuilder();

for (Character c : capital) {
    output.append(c);
}
for (Character c : simple) {
    output.append(c);
}
for (Character c : numbers) {
    output.append(c);
}

System.out.println(output.toString());

---

Вывод:

ABCabc123