webentwicklung-frage-antwort-db.com.de

Wie werden ganze Zahlen in aufsteigender Reihenfolge ohne Strings oder Arrays sortiert?

Ich versuche, die Ziffern einer ganzen Zahl in aufsteigender Reihenfolge zu sortieren, ohne Strings, Arrays oder Rekursion zu verwenden.

Beispiel:

Input: 451467
Output: 144567

Ich habe bereits herausgefunden, wie man jede Ziffer der Ganzzahl mit Modulteilung erhält:

int number = 4214;

while (number > 0) {
    IO.println(number % 10);
    number = number / 10;
}

aber ich weiß nicht, wie man die Ziffern ohne Array anordnet.

Machen Sie sich keine Sorgen über die IO-Klasse. Es ist eine benutzerdefinierte Klasse, die uns unser Professor gab.

javasortingmodulo
8
klayveR

Es gibt tatsächlich einen sehr einfachen Algorithmus, der nur Ganzzahlen verwendet:

int number = 4214173;
int sorted = 0;
int digits = 10;
int sortedDigits = 1;
boolean first = true;

while (number > 0) {
    int digit = number % 10;

    if (!first) {

        int tmp = sorted;
        int toDivide = 1;
        for (int i = 0; i < sortedDigits; i++) {
            int tmpDigit = tmp % 10;
            if (digit >= tmpDigit) {
                sorted = sorted/toDivide*toDivide*10 + digit*toDivide + sorted % toDivide;
                break;
            } else if (i == sortedDigits-1) {
                sorted = digit * digits + sorted;
            }
            tmp /= 10;
            toDivide *= 10;
        }
        digits *= 10;
        sortedDigits += 1;
    } else {
        sorted = digit;
    }

    first = false;
    number = number / 10;
}
System.out.println(sorted);

es wird 1123447..__ ausgedruckt. Die Idee ist einfach: 

  1. sie nehmen die aktuelle Ziffer der Nummer, die Sie sortieren möchten (nennen wir sie N)
  2. sie gehen alle Ziffern in der bereits sortierten Nummer durch (nennen wir es S)
  3. wenn die aktuelle Ziffer in S kleiner ist als die aktuelle Ziffer in N, fügen Sie einfach die Ziffer an der aktuellen Position in S ein. Andernfalls gehen Sie einfach zur nächsten Ziffer in S. 

Diese Version des Algorithmus kann sowohl aufsteigend als auch absteigend sortieren. Sie müssen lediglich die Bedingung ändern.

Ich schlage auch vor, einen Blick auf die sogenannte Radix Sort , die Lösung hier zu werfen, die einige Ideen von Radix Sort enthält, und ich denke, die Radix Sort ist der allgemeine Fall für diese Lösung.

6
Timofey

Es sind 4 Zeilen, basierend auf einer for-Loop-Variante Ihrer While-Schleife mit etwas Java 8-Gewürz:

int number = 4214;

List<Integer> numbers = new LinkedList<>(); // a LinkedList is not backed by an array
for (int i = number; i > 0; i /= 10)
    numbers.add(i % 10);
numbers.stream().sorted().forEach(System.out::println); // or for you forEach(IO::println)
8
Bohemian

Wie sortiere ich eine Zahl ohne Array, String oder Sortier-API? Nun, Sie können eine Zahl mit den folgenden einfachen Schritten sortieren (wenn zu viel zu lesen ist, lesen Sie unten die Debugging-Ausgabe, um eine Vorstellung davon zu erhalten, wie die Sortierung durchgeführt wird): 

  1. Holen Sie sich die letzte Ziffer der Nummer mit (digit = number% 10) 
  2. Anzahl teilen, so dass letzte Ziffer weg ist (Zahl/= 10) 
  3. Durchlaufen Sie die Ziffern der Zahl (die keine Ziffer hat) und prüfen Sie, ob die Ziffer die kleinste ist
  4. Wenn eine neue, kleinere Ziffer gefunden wurde, ersetzen Sie die Ziffer = kleinste Ziffer und suchen Sie bis zum Ende
  5. Am Ende der Schleife haben Sie die kleinste Ziffer gefunden, speichern Sie sie (store = (store * 10) + digit 
  6. Wenn Sie nun wissen, dass es sich um die kleinste Ziffer handelt, entfernen Sie diese Ziffer von der Nummer und führen Sie die oben genannten Schritte für die Restnummer durch. Jedes Mal, wenn eine kleinere Ziffer gefunden wird, fügen Sie sie dem Geschäft hinzu und entfernen Sie die Ziffer von der Nummer (wenn sich die Ziffer in der Nummer wiederholt dann entfernen Sie sie alle und fügen Sie sie zum Speichern hinzu) 

Ich habe einen Code mit zwei while-Schleifen in der Hauptmethode und einer Funktion bereitgestellt. Die Funktion tut nichts außer, baut eine neue Ganzzahl auf, mit Ausnahme der Ziffer, an die übergeben wird. Zum Beispiel übergebe ich die Funktion 451567 und 1 und die Funktion gibt mir 45567 zurück (in beliebiger Reihenfolge spielt keine Rolle). Wenn diese Funktion 451567 und 5 übergeben wird, werden beide 5-stellige Nummern gefunden und zum Speichern und zum Rückgeben der Nummer ohne 5-stellige Zeichen hinzugefügt (dies vermeidet zusätzliche Verarbeitung). 

Debugging, um zu wissen, wie die Ganzzahl sortiert wird:

Letzte Ziffer ist: 7 der Nummer: 451567
Subchunk ist 45156
Subchunk ist 4515
Subchunk ist 451
Subchunk ist 45
Subchunk ist 4
Die kleine Zahl in 451567 ist 1
Speicher ist: 1
Entferne 1 von 451567
Reduzierte Anzahl ist: 76554
Letzte Ziffer ist: 4 der Zahl: 76554
Subchunk ist 7655
Subchunk ist 765
Subchunk ist 76
Subchunk ist 7
Kleinste Ziffer in 76554 ist 4
Shop ist: 14
Entferne 4 von 76554
Reduzierte Anzahl ist: 5567
Letzte Ziffer ist: 7 der Zahl: 5567
Subchunk ist 556
Subchunk ist 55
.__ Subchunk ist 5
Kleinste Ziffer in 5567 ist 5
Speicher ist: 145
Entferne 5 von 5567
Wiederholte min Stelle 5 gefunden. Shop ist: 145
Wiederholte min. Ziffer 5 zum Speichern hinzugefügt. Neuer Shop ist: 1455
Reduzierte Anzahl ist: 76
Letzte Ziffer ist: 6 der Zahl: 76
Subchunk ist 7
Die kleinste Ziffer in 76 ist 6
Speicher ist: 14556
Entferne 6 von 76
Reduzierte Anzahl ist: 7
Letzte Ziffer ist: 7 von Nummer: 7
Kleinste Ziffer in 7 ist 7
Speicher ist: 145567
Entferne 7 von 7
Reduzierte Anzahl ist: 0
Aufsteigende Reihenfolge von 451567 ist 145567

Der Beispielcode lautet wie folgt: 

//stores our sorted number
     static int store = 0; 

     public static void main(String []args){
        int number = 451567; 
        int original = number; 

        while (number > 0) {
            //digit by digit - get last most digit
            int digit = number % 10;

            System.out.println("Last digit is : " + digit + " of number : " + number); 

            //get the whole number minus the last most digit 
            int temp = number / 10; 

            //loop through number minus the last digit to compare
            while(temp > 0) {
                System.out.println("Subchunk is " + temp); 
                //get the last digit of this sub-number
                int t = temp % 10; 

                //compare and find the lowest
                //for sorting descending change condition to t > digit
                if(t < digit)   
                    digit = t; 

                //divide the number and keep loop until the smallest is found
                temp = temp / 10;
            }
            System.out.println("Smalled digit in " + number  + " is " + digit); 

            //add the smallest digit to store 
            store = (store * 10) + digit; 

            System.out.println("Store is : " + store); 

            //we found the smallest digit, we will remove that from number and find the 
            //next smallest digit and keep doing this until we find all the smallest 
            //digit in sub chunks of number, and keep adding the smallest digits to 
            //store
            number = getReducedNumber(number, digit); 
        }
        System.out.println("Ascending order of " + original + " is " + store); 
     }


     /*
     * A simple method that constructs a new number, excluding the digit that was found
     * to b e smallest and added to the store. The new number gets returned so that 
     * smallest digit in the returned new number be found.
     */
     public static int getReducedNumber(int number, int digit) {
        System.out.println("Remove " + digit + " from " + number); 
        int newNumber = 0; 

        //flag to make sure we do not exclude repeated digits, in case there is 44
        boolean repeatFlag = false; 
        while(number > 0) {
            int t = number % 10; 
            //assume in loop one we found 1 as smallest, then we will not add one to the new number at all
            if(t != digit) {
                newNumber = (newNumber * 10) + t; 
            } else if(t == digit) {
                if(repeatFlag) {
                    System.out.println("Repeated min digit " + t + "found. Store is : " + store);
                    store = (store * 10) + t; 
                    System.out.println("Repeated min digit " + t + "added to store. Updated store is : " + store);
                    //we found another value that is equal to digit, add it straight to store, it is 
                    //guaranteed to be minimum
                } else {
                    //skip the digit because its added to the store, in main method, set flag so 
                    // if there is repeated digit then this method add them directly to store
                    repeatFlag = true; 
                }
            }
            number /= 10; 
        }
        System.out.println("Reduced number is : " + newNumber); 
        return newNumber; 
     }
}
2
Raf

Ich gehe davon aus, dass Sie Hashing verwenden dürfen.

public static void sortDigits(int x) {
    Map<Integer, Integer> digitCounts = new HashMap<>();

    while (x > 0) {
        int digit = x % 10;
        Integer currentCount = digitCounts.get(digit);
        if (currentCount == null) {
            currentCount = 0;
        }
        digitCounts.put(x % 10, currentCount + 1);
        x = x / 10;
    }

    for (int i = 0; i < 10; i++) {
        Integer count = digitCounts.get(i);
        if (count == null) {
            continue;
        }
        for (int j = 0; j < digitCounts.get(i); j++) {
            System.out.print(i);
        }
    }
}
2
tharindu_DG

Mein Algorithmus dafür:

int ascending(int a)
{
    int b = a;
    int i = 1;
    int length = (int)Math.log10(a) + 1;   // getting the number of digits
    for (int j = 0; j < length - 1; j++)
    {
        b = a;
        i = 1;
        while (b > 9)
        { 
            int s = b % 10;                // getting the last digit
            int r = (b % 100) / 10;        // getting the second last digit
            if (s < r)
            {
                a = a + s * i * 10 - s * i - r * i * 10 + r * i; // switching the digits
            }
            b = a;
            i = i * 10;
            b = b / i;                     // removing the last digit from the number
        }
    }
    return a;
}
1
Abbas

Hinzufügen eines sehr einfachen Algorithmus, der keine Datenstrukturen oder mathematischen Berechnungen erfordert, wie dies bei den anderen der Fall ist.

int number = 65356;
for (int i = 0; i <= 9; i++) { // the possible elements are known, 0 to 9
    int tempNumber = number;
    while (tempNumber > 0) {
        int digit = tempNumber % 10;
        IO.print(digit);
        tempNumber = number / 10;
    }
}

In Worten:
1. Drucke eine 0 für jede 0 in der Zahl.
2. Drucken Sie eine 1 für jede 1 in der Nummer.
...

1
Raimund Krämer
class SortDigits {
    public static void main(String[] args) {
        int inp=57437821;
        int len=Integer.toString(inp).length();
        int[] arr=new int[len];
        for(int i=0;i<len;i++)
        {
            arr[i]=inp%10;
            inp=inp/10;
        }
        Arrays.sort(arr);
        int num=0;
        for(int i=0;i<len;i++)
        {
            num=(num*10)+arr[i];
        }
        System.out.println(num);
    }    
}
0
Arun Singh

Hier ist die einfache Lösung:

    public class SortDigits
    {
        public static void main(String[] args)
        {
            sortDigits(3413657);
        }

        public static void sortDigits(int num)
        {
            System.out.println("Number  : " + num);
            String number = Integer.toString(num);
            int len = number.length(); // get length of the number
            int[] digits = new int[len];
            int i = 0;
            while (num != 0)
            {
                int digit = num % 10;
                digits[i++] = digit; // get all the digits
                num = num / 10;
            }
            System.out.println("Digit before sorting: ");
            for (int j : digits)
            {
                System.out.print(j + ",");
            }
            sort(digits);
            System.out.println("\nDigit After sorting: ");
            for (int j : digits)
            {
                System.out.print(j + ",");
            }
        }
        //simple bubble sort 
        public static void sort(int[] arr)
        {
            for (int i = 0; i < arr.length - 1; i++)
                for (int j = i + 1; j < arr.length; j++)
                {
                    if (arr[i] > arr[j])
                    {
                        int tmp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = tmp;
                    }
                }
        }
    }
0
Pushparaj Dhole