как я могу отсортировать число без использования массива? - PullRequest
Новая
       6

как я могу отсортировать число без использования массива?

0 голосов
/ 04 апреля 2019

Как найти максимальное и минимальное число, которое можно сформировать, используя цифры данного числа (например, 485735), без использования какого-либо массива вообще?

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

Единственное, что пришло мне в голову, это алгоритм подсчета количества цифр во входных данных (друг помог мне с этим), но пока я пытался разобраться с этим 4 дня. это вопрос с оценкой из моей домашней работы

правило состоит в том, что наименьшее число не может начинаться с нуля например: 

Input: 3134059 
The largest number is: 9543310
The smallest number is: 1033459

Ответы [ 2 ]

2 голосов
/ 04 апреля 2019

TL; DR: см. Демонстрацию нижеприведенной логики в IDEONE .

Представьте, что число представляет собой массив цифр, например, с именем d[], и сделайте видэтот индекс 0 является самой правой цифрой.

Пузырьковая сортировка переместит более высокие значения в более высокие индексы, поэтому, если мы сохраним эту логику, сортировка d приведет к желаемому largestNumber, например 1357924становится 9754321.

Предположим, у вас есть метод pow10(n), который вычисляет 10 n , затем вы можете получить цифру по любому индексу: 

d[i] = number / pow10(i) % 10

Пример:

         6 4 2 0  index
         ↓ ↓ ↓ ↓
number = 1357924

d[4] = 1357924 / pow10(4) % 10
     = 1357924 / 10000 % 10
     = 135 % 10
     =   5

В пузырьковой сортировке вы меняете соседние элементы, если элемент с более низким индексом больше, поэтому сначала нам понадобятся два значения.Допустим, мы делаем это для i = 3: 

         6 4 2 0  index
         ↓ ↓ ↓ ↓
number = 1357924
i = 3

a = d[i] = d[3] = 7
b = d[i+1] = d[4] = 5

Поскольку a > b, мы должны поменять значения.Мы можем сделать это следующим образом: 

 1357924
-   7000   Clear digit at i=3
-  50000   Clear digit at i=4
=1300924   Value with digits cleared
+  70000   Set digit at i=4
+   5000   Set digit at i=3
=1375924   Value with digits at index 3 and 4 swapped

Формула для этого: 

number = number - a * pow10(i) - b * pow10(i+1)
                + a * pow10(i+1) + b * pow10(i)

Который может быть изменен на: 

number += ((a - b) * 10 - (a - b)) * pow10(i)

Теперь, когда вы знаетекак получить «значение элемента массива», или d[i], и как «поменять местами элементы массива» с помощью приведенной выше формулы, вы записываете это в обычный алгоритм сортировки пузырьков, так что вы можете: 

largestNumber = sortDigits(number)

Теперь вы рассчитали наибольшее значение.Чтобы вычислить наименьшее значение, вам нужно просто поменять цифры, но прежде чем сделать это, вам нужно убедиться, что d[0] != 0: 

n = largestNumber, i = 0
while (n % 10 == 0) { // locate least non-zero digit
    n /= 10
    i++
}
if (i != 0) {
    // clear least digit and add at index 0
    n = n / 10 * pow10(i + 1) + n % 10
}

Пример: 

n = 97500
After loop: n = 975, i = 2
n / 10 = 97
            * pow10(i + 1) = 97000
                                   + n % 10 = 97005

СейчасВы можете вычислить другое необходимое вам значение: 

smallestNumber = reverse(n)

См., например, Java обратное значение типа int без использования массива , чтобы узнать, как это сделать.

0 голосов
/ 04 апреля 2019 
public static void main(String[] args) {

    StringBuilder s = new StringBuilder("4857035");
    char aux;

    for (int i = 0; i < s.length() - 1; i++) {
        for (int j = i + 1; j < s.length(); j++) {
            if (s.charAt(i) > (s.charAt(j))) {
                aux = s.charAt(i);
                s.setCharAt(i, s.charAt(j));
                s.setCharAt(j, aux);
            }
        }
    }
    //output 0345578

    while (s.charAt(0) == '0') {
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                aux = s.charAt(0);
                s.setCharAt(0, s.charAt(i));
                s.setCharAt(i, aux);
                break;
            }
        }
    }
    //output 3045578
}

Это для наименьшего числа, для наибольшего числа измените знак оператора if (if (s.charAt(i) < (s.charAt(j))) и удалите оператор while.

...