Suchen Sie bei gegebener Nummer die nächsthöhere Nummer, die genau die gleichen Ziffern wie die ursprüngliche Nummer hat

Ich habe gerade ein Interview bombardiert und bei meiner Interviewfrage so gut wie keine Fortschritte gemacht. Kann mir jemand mitteilen, wie das geht? Ich habe versucht, online zu suchen, konnte aber nichts finden:

Suchen Sie bei gegebener Nummer die nächsthöhere Nummer, die genau die gleichen Ziffern wie die ursprüngliche Nummer hat. Zum Beispiel: gegeben 38276 return 38627

Ich wollte zunächst den Index der ersten Ziffer (von rechts) finden, der kleiner als die Ziffer war. Dann würde ich die letzten Ziffern in der Teilmenge so drehen, dass es die nächstgrößere Zahl war, die aus denselben Ziffern bestand, aber stecken blieb.

Der Interviewer schlug auch vor, die Ziffern einzeln auszutauschen, aber ich konnte den Algorithmus nicht herausfinden und starrte nur etwa 20 bis 30 Minuten lang auf einen Bildschirm. Unnötig zu sagen, ich denke, ich muss die Jobsuche fortsetzen.

edit: für was es wert ist, ich wurde zur nächsten Runde von Interviews eingeladen

Sie können dies folgendermaßen tun O(n)(wo nist die Anzahl der Ziffern):

Ausgehend von rechts finden Sie das erste Ziffernpaar so, dass die linke Ziffer kleiner als die rechte Ziffer ist. Beziehen wir uns auf die linke Ziffer mit "digit-x". Suchen Sie die kleinste Zahl größer als Ziffer-x rechts von Ziffer-x und platzieren Sie sie unmittelbar links von Ziffer-x. Sortieren Sie abschließend die verbleibenden Ziffern in aufsteigender Reihenfolge - da sie bereits in absteigender Reihenfolge waren, müssen Sie sie nur umkehren (außer für Ziffer-x, die an der richtigen Stelle in platziert werden kann O(n)) .

Ein Beispiel wird dies deutlicher machen:

123456784987654321
Beginnen Sie mit einer Zahl

123456784 987654321
         ^ die erste Stelle von rechts, wo die linke Ziffer kleiner als die rechte ist  
         Die Ziffer "x" ist 4

123456784 987654321
              ^ Finde die kleinste Ziffer größer als 4 rechts

123456785 4 98764321
        ^ Platziere es links von 4

123456785 4 12346789
123456785123446789
         ^ sortiere die Ziffern rechts von 5. Da alle außer 
         Die '4' waren bereits in absteigender Reihenfolge, alles was wir tun müssen ist 
         kehre ihre Reihenfolge um und finde den richtigen Platz für die '4'

Korrektheitsnachweis:

Verwenden wir Großbuchstaben, um Ziffernfolgen und Kleinbuchstaben für Ziffern zu definieren. Die Syntax ABbedeutet "die Verkettung von Zeichenfolgen Aund B" . <ist die lexikografische Reihenfolge, die der ganzzahligen Reihenfolge entspricht, wenn die Ziffernfolgen gleich lang sind.

Unsere ursprüngliche Nummer N hat die Form AxB, wobei xes sich um eine einzelne Ziffer Bhandelt, die absteigend sortiert ist.
Die Zahl gefunden von unserem Algorithmus ist AyC, wo y ∈ Bist die kleinste Ziffer > x (es existieren muss aufgrund der Art und Weise xoben gewählt wurde, sehen) , und Cwird sortiert aufsteigend.

Angenommen, es gibt eine Zahl (mit denselben Ziffern), N'so dass AxB < N' < AyC. N'muss damit beginnen Aoder es könnte nicht zwischen sie fallen, damit wir es in der Form schreiben können AzD. Jetzt ist unsere Ungleichung AxB < AzD < AyCgleichbedeutend damit, xB < zD < yCdass alle drei Ziffernfolgen die gleichen Ziffern enthalten.

Damit das wahr ist, müssen wir haben x <= z <= y. Da yist die kleinste Ziffer > x, zkann nicht zwischen ihnen sein, also entweder z = xoder z = y. Sagen Sie z = x. Dann ist unsere Ungleichung xB < xD < yC, was bedeutet, B < Dwo beide Bund Ddie gleichen Ziffern haben. Jedoch ist B Absteigen sortiert, so dass es ist keine Zeichenfolge mit diesen Ziffern größer , als es. Also können wir nicht haben B < D. Wenn z = ywir die gleichen Schritte ausführen, sehen wir, dass wir es nicht haben können D < C.

Daher N'kann es nicht existieren, was bedeutet, dass unser Algorithmus die nächstgrößere Zahl korrekt findet.

Ein fast identisches Problem trat als Code Jam-Problem auf und hat hier eine Lösung:

http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1

Hier ist eine Zusammenfassung der Methode anhand eines Beispiels:

34722641

A. Teilen Sie die Ziffernfolge in zwei Teile, damit der rechte Teil so lang wie möglich ist und in absteigender Reihenfolge bleibt:

34722 641

(Wenn die gesamte Zahl in absteigender Reihenfolge vorliegt, kann keine größere Zahl ohne Hinzufügen von Ziffern erstellt werden.)

B.1. Wählen Sie die letzte Ziffer der ersten Sequenz:

3472(2) 641

B.2. Suchen Sie die kleinste Ziffer in der zweiten Sequenz, die größer ist als sie:

3472(2) 6(4)1

B.3. Tauschen Sie sie aus:

3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621

C. Sortieren Sie die zweite Sequenz in aufsteigender Reihenfolge:

34724 126

D. Fertig!

34724126

Hier ist eine kompakte (aber teilweise Brute Force) Lösung in Python

def findnext(ii): return min(v for v in (int("".join(x)) for x in
    itertools.permutations(str(ii))) if v>ii)

In C ++ können Sie die Permutationen wie folgt vornehmen: https://stackoverflow.com/a/9243091/1149664 (Es ist der gleiche Algorithmus wie in itertools)

Hier ist eine Implementierung der von Weeble und BlueRaja beschriebenen Top-Antwort (andere Antworten). Ich bezweifle, dass es etwas Besseres gibt.

def findnext(ii):
    iis=list(map(int,str(ii)))
    for i in reversed(range(len(iis))):
        if i == 0: return ii
        if iis[i] > iis[i-1] :
            break        
    left,right=iis[:i],iis[i:]
    for k in reversed(range(len(right))):
        if right[k]>left[-1]:
           right[k],left[-1]=left[-1],right[k]
           break
    return int("".join(map(str,(left+sorted(right)))))

Hier sind mindestens ein paar Beispiele für Brute-Force-String-basierte Lösungen, die Sie sich auf Anhieb hätten einfallen lassen müssen:

Die Liste der Ziffern in 38276sortiert ist23678

Die Liste der Ziffern in 38627sortiert ist23678

Brute-Force-Inkrementierung, Sortierung und Vergleich

Entlang der Brute-Force-Lösung würden alle möglichen Zahlen unter Verwendung dieser Ziffern in einen String konvertiert und Brute-Force-Lösungen erzwungen.

Erstellen Sie Ints aus allen, fügen Sie sie in eine Liste ein und sortieren Sie sie. Erhalten Sie den nächsten Eintrag nach dem Zieleintrag.

Wenn Sie 30 Minuten damit verbracht hätten und sich nicht mindestens einen Brute-Force-Ansatz ausgedacht hätten, würde ich Sie auch nicht einstellen.

In der Geschäftswelt ist eine Lösung, die unelegant, langsam und klobig ist, aber die Arbeit erledigt, immer wertvoller als gar keine Lösung. Tatsächlich beschreibt sie so ziemlich jede Geschäftssoftware, unelegant, langsam und klobig.

function foo(num){
 sortOld = num.toString().split("").sort().join('');
 do{
    num++;
   sortNew = num.toString().split("").sort().join('');
 }while(sortNew!==sortOld);
 return num;
}

Deine Idee

Ich wollte zunächst den Index der ersten Ziffer (von rechts) finden, der kleiner als die Ziffer war. Dann würde ich die letzten Ziffern in der Teilmenge so drehen, dass es die nächstgrößere Zahl war, die aus denselben Ziffern bestand, aber stecken blieb.

ist eigentlich ziemlich gut. Sie müssen nur nicht nur die letzte Ziffer berücksichtigen, sondern alle Ziffern von geringerer Bedeutung als die aktuell berücksichtigte. Da wir vorher eine monotone Folge von Ziffern haben, ist dies die am weitesten rechts stehende Ziffer, die kleiner ist als ihr rechter Nachbar. Betrachten

1234675
    ^

Die nächstgrößere Zahl mit den gleichen Ziffern ist

1234756

Die gefundene Ziffer wird gegen die letzte Ziffer ausgetauscht - die kleinste der betrachteten Ziffern - und die verbleibenden Ziffern werden in aufsteigender Reihenfolge angeordnet.

Ich bin mir ziemlich sicher, dass Ihr Interviewer versucht hat, Sie sanft zu so etwas zu drängen:

local number = 564321;

function split(str)
    local t = {};
    for i = 1, string.len(str) do
        table.insert(t, str.sub(str,i,i));
    end
    return t;
end

local res = number;
local i = 1;
while number >= res do
    local t = split(tostring(res));
    if i == 1 then
        i = #t;
    end
    t[i], t[i-1] = t[i-1], t[i];
    i = i - 1;
    res = tonumber(table.concat(t));
end

print(res);

Nicht unbedingt die effizienteste oder eleganteste Lösung, aber sie löst das bereitgestellte Beispiel in zwei Zyklen und tauscht die Ziffern nacheinander aus, wie er vorgeschlagen hat.

Nehmen Sie eine Zahl und teilen Sie sie in Ziffern auf. Wenn wir also eine 5-stellige Nummer haben, haben wir 5 Ziffern: abcde

Tauschen Sie nun d und e aus und vergleichen Sie sie mit der ursprünglichen Nummer. Wenn diese größer ist, haben Sie Ihre Antwort.

Wenn es nicht größer ist, tauschen Sie e und c. Vergleichen Sie nun und wenn es kleiner ist, tauschen Sie d und e erneut aus (beachten Sie die Rekursion), nehmen Sie die kleinste.

Fahren Sie fort, bis Sie eine größere Anzahl finden. Bei der Rekursion sollten sich ungefähr 9 Schemazeilen oder 20 von c # ergeben.

Das ist eine sehr interessante Frage.

Hier ist meine Java-Version. Ich brauche ungefähr 3 Stunden, um das Muster vollständig fertigzustellen, bevor ich die Kommentare anderer Mitwirkender überprüft habe. Ich bin froh zu sehen, dass meine Idee mit anderen ganz gleich ist.

O (n) Lösung. Ehrlich gesagt, ich werde dieses Interview nicht bestehen, wenn die Zeit nur 15 Minuten beträgt und eine vollständige Code-Fertigstellung auf der weißen Tafel erforderlich ist.

Hier sind einige interessante Punkte für meine Lösung:

• Sortieren vermeiden.
• Vermeiden Sie den String-Betrieb vollständig
• Erreichen Sie die Komplexität des O (logN) -Raums

Ich habe in meinen Code einen detaillierten Kommentar und in jedem Schritt das große O eingefügt.

  public int findNextBiggestNumber(int input  )   {
    //take 1358642 as input for example.
    //Step 1: split the whole number to a list for individual digital   1358642->[2,4,6,8,5,3,1]
    // this step is O(n)
    int digitalLevel=input;

    List<Integer> orgNumbersList=new ArrayList<Integer>()   ;

    do {
        Integer nInt = new Integer(digitalLevel % 10);
        orgNumbersList.add(nInt);

        digitalLevel=(int) (digitalLevel/10  )  ;


    } while( digitalLevel >0)    ;
    int len= orgNumbersList.size();
    int [] orgNumbers=new int[len]  ;
    for(int i=0;i<len;i++){
        orgNumbers[i ]  =  orgNumbersList.get(i).intValue();
    }
    //step 2 find the first digital less than the digital right to it
    // this step is O(n)


    int firstLessPointer=1;
    while(firstLessPointer<len&&(orgNumbers[firstLessPointer]>orgNumbers[ firstLessPointer-1 ])){
        firstLessPointer++;
    }
     if(firstLessPointer==len-1&&orgNumbers[len-1]>=orgNumbers[len-2]){
         //all number is in sorted order like 4321, no answer for it, return original
         return input;
     }

    //when step 2 step finished, firstLessPointer  pointing to number 5

     //step 3 fristLessPointer found, need to find  to  first number less than it  from low digital in the number
    //This step is O(n)
    int justBiggerPointer=  0 ;

    while(justBiggerPointer<firstLessPointer&& orgNumbers[justBiggerPointer]<orgNumbers[firstLessPointer]){
        justBiggerPointer++;
    }
    //when step 3 finished, justBiggerPointer  pointing to 6

    //step 4 swap the elements  of justBiggerPointer and firstLessPointer .
    // This  is O(1) operation   for swap

   int tmp=  orgNumbers[firstLessPointer] ;

    orgNumbers[firstLessPointer]=  orgNumbers[justBiggerPointer]  ;
     orgNumbers[justBiggerPointer]=tmp ;


     // when step 4 finished, the list looks like        [2,4,5,8,6,3,1]    the digital in the list before
     // firstLessPointer is already sorted in our previous operation
     // we can return result from this list  but  in a differrent way
    int result=0;
    int i=0;
    int lowPointer=firstLessPointer;
    //the following pick number from list from  the position just before firstLessPointer, here is 8 -> 5 -> 4 -> 2
    //This Operation is O(n)
    while(lowPointer>0)        {
        result+= orgNumbers[--lowPointer]* Math.pow(10,i);
        i++;
    }
    //the following pick number from list   from position firstLessPointer
    //This Operation is O(n)
    while(firstLessPointer<len)        {
        result+= orgNumbers[firstLessPointer++ ]* Math.pow(10,i);
        i++;
    }
     return  result;

}

Hier ist das Ergebnis, das in Intellj ausgeführt wird:

959879532-->959892357
1358642-->1362458
1234567-->1234576
77654321-->77654321
38276-->38627
47-->74

Eine Javascript-Implementierung des @ BlueRaja-Algorithmus.

var Bar = function(num){ 
  num = num.toString();
  var max = 0;
  for(var i=num.length-2; i>0; i--){
    var numArray = num.substr(i).split("");
    max = Math.max.apply(Math,numArray);
    if(numArray[0]<max){
        numArray.sort(function(a,b){return a-b;});
        numArray.splice(-1);
        numArray = numArray.join("");
        return Number(num.substr(0,i)+max+numArray);
    }
  }
  return -1;
};

Eine Lösung (in Java) könnte die folgende sein (ich bin sicher, dass Freunde hier eine bessere finden können):
Tauschen Sie die Ziffern am Ende der Zeichenfolge aus, bis Sie eine höhere Zahl erhalten.
Dh zuerst die niedrigere Ziffer nach oben bewegen. Dann die nächsthöhere usw., bis Sie die nächsthöhere treffen.
Dann sortieren Sie den Rest. In Ihrem Beispiel würden Sie erhalten:

38276 --> 38267 (smaller) --> 38627 Found it    
    ^        ^                  ^        

 public static int nextDigit(int number){
    String num = String.valueOf(number);        
    int stop = 0;       
    char [] chars = null;
    outer:
        for(int i = num.length() - 1; i > 0; i--){          
            chars = num.toCharArray();
            for(int j = i; j > 0; j--){
                char temp = chars[j];
                chars[j] = chars[j - 1];
                chars[j - 1] = temp;
                if(Integer.valueOf(new String(chars)) > number){
                    stop = j;                   
                    break outer;                                
                }               
            }               
        }

    Arrays.sort(chars, stop, chars.length); 
    return Integer.valueOf(new String(chars));
}

Wenn Sie in C ++ programmieren, können Sie Folgendes verwenden next_permutation:

#include <algorithm>
#include <string>
#include <iostream>

int main(int argc, char **argv) {
  using namespace std; 
   string x;
   while (cin >> x) {
    cout << x << " -> ";
    next_permutation(x.begin(),x.end());
    cout << x << "\n";
  }
  return 0;
}

Ich wusste nichts über den Brute-Force-Algorithmus, als ich diese Frage beantwortete, also näherte ich mich ihm aus einem anderen Blickwinkel. Ich habe mich entschlossen, die gesamte Palette möglicher Lösungen zu durchsuchen, in die diese Nummer möglicherweise umgeordnet werden könnte, angefangen von number_given + 1 bis zur maximal verfügbaren Nummer (999 für eine dreistellige Nummer, 9999 für 4 Ziffern usw.). Ich habe so etwas wie ein Palindrom mit Wörtern gefunden, indem ich die Zahlen jeder Lösung sortiert und mit der als Parameter angegebenen sortierten Zahl verglichen habe. Ich habe dann einfach die erste Lösung im Array der Lösungen zurückgegeben, da dies der nächstmögliche Wert wäre.

Hier ist mein Code in Ruby:

def PermutationStep(num)

    a = []
    (num.to_s.length).times { a.push("9") }
    max_num = a.join('').to_i
    verify = num.to_s.split('').sort
    matches = ((num+1)..max_num).select {|n| n.to_s.split('').sort == verify }

    if matches.length < 1
      return -1
    else
      matches[0]
    end
end

PHP-Code

function NextHigherNumber($num1){
$num = strval($num1);
$max = 0;
for($i=(strlen($num)-2); $i>=0; $i--){
    $numArrayRaw = substr($num, $i);
    $numArray = str_split($numArrayRaw);
    $max = max($numArray);
    if ($numArray[0] < $max){
        sort( $numArray, SORT_NUMERIC );
        array_pop($numArray);
        $numarrstr = implode("",$numArray);
        $rt = substr($num,0,$i) . $max . $numarrstr;
        return $rt;
    }
}
return "-1";
}
echo NextHigherNumber(123);

Ich habe das nur mit zwei Zahlen getestet. Sie arbeiteten. Als IT-Manager für 8 Jahre bis zu meiner Pensionierung im vergangenen Dezember habe ich mich um drei Dinge gekümmert: 1) Genauigkeit: Es ist gut, wenn es funktioniert - immer. 2) Geschwindigkeit: muss für den Benutzer akzeptabel sein. 3) Klarheit: Ich bin wahrscheinlich nicht so schlau wie du, aber ich bezahle dich. Stellen Sie sicher, dass Sie auf Englisch erklären, was Sie tun.

Omar, viel Glück für die Zukunft.

Sub Main()

Dim Base(0 To 9) As Long
Dim Test(0 To 9) As Long

Dim i As Long
Dim j As Long
Dim k As Long
Dim ctr As Long

Const x As Long = 776914648
Dim y As Long
Dim z As Long

Dim flag As Boolean

' Store the digit count for the original number in the Base vector.
    For i = 0 To 9
        ctr = 0
        For j = 1 To Len(CStr(x))
            If Mid$(CStr(x), j, 1) = i Then ctr = ctr + 1
        Next j
        Base(i) = ctr
    Next i

' Start comparing from the next highest number.
    y = x + 1
    Do

' Store the digit count for the each new number in the Test vector.
        flag = False
        For i = 0 To 9
            ctr = 0
            For j = 1 To Len(CStr(y))
                If Mid$(CStr(y), j, 1) = i Then ctr = ctr + 1
            Next j
            Test(i) = ctr
        Next i

' Compare the digit counts.
        For k = 0 To 9
            If Test(k) <> Base(k) Then flag = True
        Next k

' If no match, INC and repeat.
        If flag = True Then
            y = y + 1
            Erase Test()
        Else
            z = y ' Match.
        End If

    Loop Until z > 0

    MsgBox (z), , "Solution"

End Sub

Eine ausführliche Beschreibung dazu finden Sie unter " Algorithmus L " in Knuths " Die Kunst der Computerprogrammierung: Generieren aller Permutationen " (.ps.gz).

Hier ist mein Code, es ist eine modifizierte Version dieses Beispiels

Bibliothek:

class NumPermExample
{
    // print N! permutation of the characters of the string s (in order)
    public  static void perm1(String s, ArrayList<String> perm)
    {
        perm1("", s);
    }

    private static void perm1(String prefix, String s, ArrayList<String> perm)
    {
        int N = s.length();
        if (N == 0)
        {
            System.out.println(prefix);
            perm.add(prefix);
        }
        else
        {
            for (int i = 0; i < N; i++)
                perm1(prefix + s.charAt(i), s.substring(0, i)
                    + s.substring(i+1, N));
        }

    }

    // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s, ArrayList<String> perm)
    {
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n, ArrayList<String> perm)
    {
        if (n == 1)
        {
            System.out.println(a);
            perm.add(new String(a));
            return;
        }

        for (int i = 0; i < n; i++)
        {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }  

    // swap the characters at indices i and j
    private static void swap(char[] a, int i, int j)
    {
        char c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }

    // next higher permutation
    public static int nextPermutation (int number)
    {
        ArrayList<String> perm = new ArrayList<String>();

        String cur = ""+number;

        int nextPerm = 0;

        perm1(cur, perm);

        for (String s : perm)
        {
            if (Integer.parseInt(s) > number
                        && (nextPerm == 0 ||
                            Integer.parseInt(s) < nextPerm))
            {
                nextPerm = Integer.parseInt(s);
            }
        }

            return nextPerm;
    }
}

Prüfung:

public static void main(String[] args) 
{
    int a = 38276;

    int b = NumPermExample.nextPermutation(a);

    System.out.println("a: "+a+", b: "+b);
}

Addiere 9 zu der angegebenen n-stelligen Nummer. Überprüfen Sie dann, ob es innerhalb des Grenzwerts liegt (die erste (n + 1) Ziffernzahl). Wenn dies der Fall ist, prüfen Sie, ob die Ziffern in der neuen Nummer mit den Ziffern in der ursprünglichen Nummer übereinstimmen. Wiederholen Sie das Hinzufügen von 9, bis beide Bedingungen erfüllt sind. Stoppen Sie den Algo, wenn die Anzahl das Limit überschreitet.

Ich konnte keinen widersprüchlichen Testfall für diese Methode finden.

Nur eine andere Lösung mit Python:

def PermutationStep(num):
    if sorted(list(str(num)), reverse=True) == list(str(num)):
        return -1
    ls = list(str(num))
    n = 0
    inx = 0
    for ind, i in enumerate(ls[::-1]):
        if i < n:
            n = i
            inx = -(ind + 1)
            break
        n = i
    ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]

    nl = ls[inx::-1][::-1]
    ln = sorted(ls[inx+1:])
    return ''.join(nl) + ''.join(ln)

print PermutationStep(23514)

Ausgabe:

23541

public static void findNext(long number){

        /* convert long to string builder */    

        StringBuilder s = new StringBuilder();
        s.append(number);
        int N = s.length();
        int index=-1,pivot=-1;

/* from tens position find the number (called pivot) less than the number in right */ 

        for(int i=N-2;i>=0;i--){

             int a = s.charAt(i)-'0';
             int b = s.charAt(i+1)-'0';

             if(a<b){
                pivot = a;
                index =i;
                break;
            }
        }

      /* if no such pivot then no solution */   

        if(pivot==-1) System.out.println(" No such number ")

        else{   

     /* find the minimum highest number to the right higher than the pivot */

            int nextHighest=Integer.MAX_VALUE, swapIndex=-1;

            for(int i=index+1;i<N;i++){

            int a = s.charAt(i)-'0';

            if(a>pivot && a<nextHighest){
                    nextHighest = a;
                    swapIndex=i;
                }
            }


     /* swap the pivot and next highest number */

            s.replace(index,index+1,""+nextHighest);
            s.replace(swapIndex,swapIndex+1,""+pivot);

/* sort everything to right of pivot and replace the sorted answer to right of pivot */

            char [] sort = s.substring(index+1).toCharArray();
            Arrays.sort(sort);

            s.replace(index+1,N,String.copyValueOf(sort));

            System.out.println("next highest number is "+s);
        }

    }

Unten ist der Code, um alle Permutationen einer Zahl zu generieren. Allerdings muss man diese Ganzzahl zuerst mit String.valueOf (Ganzzahl) in einen String konvertieren.

/**
 * 
 * Inserts a integer at any index around string.
 * 
 * @param number
 * @param position
 * @param item
 * @return
 */
public String insertToNumberStringAtPosition(String number, int position,
        int item) {
    String temp = null;
    if (position >= number.length()) {
        temp = number + item;
    } else {
        temp = number.substring(0, position) + item
                + number.substring(position, number.length());
    }
    return temp;
}

/**
 * To generate permutations of a number.
 * 
 * @param number
 * @return
 */
public List<String> permuteNumber(String number) {
    List<String> permutations = new ArrayList<String>();
    if (number.length() == 1) {
        permutations.add(number);
        return permutations;
    }
    // else
    int inserterDig = (int) (number.charAt(0) - '0');
    Iterator<String> iterator = permuteNumber(number.substring(1))
            .iterator();
    while (iterator.hasNext()) {
        String subPerm = iterator.next();
        for (int dig = 0; dig <= subPerm.length(); dig++) {
            permutations.add(insertToNumberStringAtPosition(subPerm, dig,
                    inserterDig));
        }
    }
    return permutations;
}

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int i,j,k,min,len,diff,z,u=0,f=0,flag=0;
    char temp[100],a[100]`enter code here`,n;
    min=9999;
    //cout<<"Enter the number\n";
    cin>>a;
    len=strlen(a);
    for(i=0;i<len;i++)
    {
        if(a[i]<a[i+1]){flag=1;break;}
    }
    if(flag==0){cout<<a<<endl;}
    else
    {
        for(i=len-1;i>=0;i--)if(((int)a[i-1])<((int)a[i]))break;
        for(k=0;k<i-1;k++)cout<<a[k];
        for(j=i;j<len;j++)
        {
            if(((int)a[j]-48)-((int)a[i-1]-48)>0)
            {
                diff=((int)a[j]-48)-((int)a[i-1]-48);
                if(diff<min){n=a[j];min=diff;}
            }
        }
        cout<<n;
        for(z=i-1;z<len;z++)
        {
            temp[u]=a[z];
            u++;
        }
        temp[u]='\0';
        sort(temp,temp+strlen(temp));
        for(z=0;z<strlen(temp);z++){if(temp[z]==n&&f==0){f=1;continue;}cout<<temp[z];}
    }
    return 0;
}

Eine weitere Java-Implementierung, die sofort ausgeführt werden kann und mit Tests abgeschlossen wurde. Diese Lösung ist O (n) Raum und Zeit unter Verwendung einer guten alten dynamischen Programmierung.

Wenn man Bruteforce betreiben möchte, gibt es zwei Arten von Bruteforce:

1. Erlaube alle Dinge und wähle dann min höher: O (n!)

2. Ähnlich wie bei dieser Implementierung, jedoch anstelle von DP, wird das Bruteforcen des Schritts zum Auffüllen der indexToIndexOfNextSmallerLeft-Map in O (n ^ 2) ausgeführt.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NextHigherSameDigits {

    public long next(final long num) {
        final char[] chars = String.valueOf(num).toCharArray();
        final int[] digits = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            digits[i] = Character.getNumericValue(chars[i]);
        }

        final Map<Integer, Integer> indexToIndexOfNextSmallerLeft = new HashMap<>();
        indexToIndexOfNextSmallerLeft.put(1, digits[1] > digits[0] ? 0 : null);
        for (int i = 2; i < digits.length; i++) {
            final int left = digits[i - 1];
            final int current = digits[i];
            Integer indexOfNextSmallerLeft = null;
            if (current > left) {
                indexOfNextSmallerLeft = i - 1;
            } else {
                final Integer indexOfnextSmallerLeftOfLeft = indexToIndexOfNextSmallerLeft.get(i - 1);
                final Integer nextSmallerLeftOfLeft = indexOfnextSmallerLeftOfLeft == null ? null : 
                    digits[indexOfnextSmallerLeftOfLeft];

                if (nextSmallerLeftOfLeft != null && current > nextSmallerLeftOfLeft) {
                    indexOfNextSmallerLeft = indexOfnextSmallerLeftOfLeft;
                } else {
                    indexOfNextSmallerLeft = null;
                }
            }

            indexToIndexOfNextSmallerLeft.put(i, indexOfNextSmallerLeft);
        }

        Integer maxOfindexOfNextSmallerLeft = null;
        Integer indexOfMinToSwapWithNextSmallerLeft = null;
        for (int i = digits.length - 1; i >= 1; i--) {
            final Integer indexOfNextSmallerLeft = indexToIndexOfNextSmallerLeft.get(i);
            if (maxOfindexOfNextSmallerLeft == null ||
                    (indexOfNextSmallerLeft != null && indexOfNextSmallerLeft > maxOfindexOfNextSmallerLeft)) {

                maxOfindexOfNextSmallerLeft = indexOfNextSmallerLeft;
                if (maxOfindexOfNextSmallerLeft != null && (indexOfMinToSwapWithNextSmallerLeft == null || 
                        digits[i] < digits[indexOfMinToSwapWithNextSmallerLeft])) {

                    indexOfMinToSwapWithNextSmallerLeft = i;
                }
            }
        }

        if (maxOfindexOfNextSmallerLeft == null) {
            return -1;
        } else {
            swap(digits, indexOfMinToSwapWithNextSmallerLeft, maxOfindexOfNextSmallerLeft);
            reverseRemainingOfArray(digits, maxOfindexOfNextSmallerLeft + 1);
            return backToLong(digits);
        }
    }

    private void reverseRemainingOfArray(final int[] digits, final int startIndex) {
        final int[] tail = Arrays.copyOfRange(digits, startIndex, digits.length);
        for (int i = tail.length - 1; i >= 0; i--) {
            digits[(digits.length - 1)  - i] = tail[i];                 
        }
    }

    private void swap(final int[] digits, final int currentIndex, final int indexOfNextSmallerLeft) {
        int temp = digits[currentIndex];
        digits[currentIndex] = digits[indexOfNextSmallerLeft];
        digits[indexOfNextSmallerLeft] = temp;
    }

    private long backToLong(int[] digits) {     
        StringBuilder sb = new StringBuilder();
        for (long i : digits) {
            sb.append(String.valueOf(i));
        }

        return Long.parseLong(sb.toString());
    }

    @Test
    public void test() {
        final long input1 =    34722641;
        final long expected1 = 34724126;
        final long output1 = new NextHigherSameDigits().next(input1);
        assertEquals(expected1, output1);

        final long input2 =    38276;
        final long expected2 = 38627;
        final long output2 = new NextHigherSameDigits().next(input2);
        assertEquals(expected2, output2);

        final long input3 =    54321;
        final long expected3 = -1;
        final long output3 = new NextHigherSameDigits().next(input3);
        assertEquals(expected3, output3);

        final long input4 =    123456784987654321L;
        final long expected4 = 123456785123446789L;
        final long output4 = new NextHigherSameDigits().next(input4);
        assertEquals(expected4, output4);

        final long input5 =    9999;
        final long expected5 = -1;
        final long output5 = new NextHigherSameDigits().next(input5);
        assertEquals(expected5, output5);
    }

}

Wir müssen das am weitesten rechts stehende Bit 0 gefolgt von einer 1 finden und dieses am weitesten rechts stehende 0-Bit auf eine 1 drehen.

Nehmen wir zum Beispiel an, unsere Eingabe ist 487, was 111100111 in Binärform ist.

Wir drehen die 0 ganz rechts um, auf die 1 folgt

so bekommen wir 111101111

Aber jetzt haben wir eine zusätzliche 1 und eine weniger 0, also reduzieren wir die Anzahl der Einsen rechts vom Flip-Bit um 1 und erhöhen die Anzahl der 0-Bits um 1, was ergibt

111101011 - binär 491

int getNextNumber(int input)
{
    int flipPosition=0;
    int trailingZeros=0;
    int trailingOnes=0;
    int copy = input;

    //count trailing zeros
    while(copy != 0 && (copy&1) == 0 )
    {
        ++trailingZeros;

        //test next bit
        copy = copy >> 1;
    }

    //count trailing ones
    while(copy != 0 && (copy&1) == 1 )
    {
        ++trailingOnes;

        //test next bit
        copy = copy >> 1;
    }

    //if we have no 1's (i.e input is 0) we cannot form another pattern with 
    //the same number of 1's which will increment the input, or if we have leading consecutive
    //ones followed by consecutive 0's up to the maximum bit size of a int
    //we cannot increase the input whilst preserving the original no of 0's and
    //1's in the bit pattern
    if(trailingZeros + trailingOnes  == 0 || trailingZeros + trailingOnes == 31)
        return -1;

    //flip first 0 followed by a 1 found from the right of the bit pattern
    flipPosition = trailingZeros + trailingOnes+1;
    input |= 1<<(trailingZeros+trailingOnes);

    //clear fields to the right of the flip position
    int mask = ~0 << (trailingZeros+trailingOnes);
    input &= mask;

    //insert a bit pattern to the right of the flip position that will contain
    //one less 1 to compensate for the bit we switched from 0 to 1
    int insert = flipPosition-1;
    input |= insert;

    return input;
}

int t,k,num3,num5;
scanf("%d",&t);
int num[t];
for(int i=0;i<t;i++){
    scanf("%d",&num[i]);   
}
for(int i=0;i<t;i++){
    k=(((num[i]-1)/3)+1); 
    if(k<0)
        printf("-1");
    else if(num[i]<3 || num[i]==4 || num[i]==7)
        printf("-1");
    else{
        num3=3*(2*num[i] - 5*k);
        num5=5*(3*k -num[i]);
        for(int j=0;j<num3;j++)
            printf("5");
        for(int j=0;j<num5;j++)
            printf("3");
    }
    printf("\n");
}

Hier ist die Java-Implementierung

public static int nextHigherNumber(int number) {
    Integer[] array = convertToArray(number);
    int pivotIndex = pivotMaxIndex(array);
    int digitInFirstSequence = pivotIndex -1;
    int lowerDigitIndexInSecondSequence = lowerDigitIndex(array[digitInFirstSequence], array, pivotIndex);
    swap(array, digitInFirstSequence, lowerDigitIndexInSecondSequence);
    doRercursiveQuickSort(array, pivotIndex, array.length - 1);
    return arrayToInteger(array);
}

public static Integer[] convertToArray(int number) {
    int i = 0;
    int length = (int) Math.log10(number);
    int divisor = (int) Math.pow(10, length);
    Integer temp[] = new Integer[length + 1];

    while (number != 0) {
        temp[i] = number / divisor;
        if (i < length) {
            ++i;
        }
        number = number % divisor;
        if (i != 0) {
            divisor = divisor / 10;
        }
    }
    return temp;
}

private static int pivotMaxIndex(Integer[] array) {
    int index = array.length - 1;
    while(index > 0) {
        if (array[index-1] < array[index]) {
            break;
        }
        index--;
    }       
    return index;
}

private static int lowerDigitIndex(int number, Integer[] array, int fromIndex) {
    int lowerMaxIndex = fromIndex;
    int lowerMax = array[lowerMaxIndex];
    while (fromIndex < array.length - 1) {
        if (array[fromIndex]> number && lowerMax > array[fromIndex]) {
            lowerMaxIndex = fromIndex; 
        }
        fromIndex ++;
    }
    return lowerMaxIndex;
}

public static int arrayToInteger(Integer[] array) {
    int number = 0;
    for (int i = 0; i < array.length; i++) {
        number+=array[i] * Math.pow(10, array.length-1-i);
    }
    return number;
}

Hier sind die Unit Tests

@Test
public void nextHigherNumberTest() {
    assertThat(ArrayUtils.nextHigherNumber(34722641), is(34724126));
    assertThat(ArrayUtils.nextHigherNumber(123), is(132));
}

Ich weiß, dass dies eine sehr alte Frage ist, aber ich habe in c # immer noch keinen einfachen Code gefunden. Dies könnte Leuten helfen, die an Interviews teilnehmen.

class Program
{
    static void Main(string[] args)
    {

        int inputNumber = 629;
        int i, currentIndexOfNewArray = 0;

        int[] arrayOfInput = GetIntArray(inputNumber);
        var numList = arrayOfInput.ToList();

        int[] newArray = new int[arrayOfInput.Length];

        do
        {
            int temp = 0;
            int digitFoundAt = 0;
            for (i = numList.Count; i > 0; i--)
            {
                if (numList[i - 1] > temp)
                {
                    temp = numList[i - 1];
                    digitFoundAt = i - 1;
                }
            }

            newArray[currentIndexOfNewArray] = temp;
            currentIndexOfNewArray++;
            numList.RemoveAt(digitFoundAt);
        } while (arrayOfInput.Length > currentIndexOfNewArray);



        Console.WriteLine(GetWholeNumber(newArray));

        Console.ReadKey();


    }

    public static int[] GetIntArray(int num)
    {
        IList<int> listOfInts = new List<int>();
        while (num > 0)
        {
            listOfInts.Add(num % 10);
            num = num / 10;
        }
        listOfInts.Reverse();
        return listOfInts.ToArray();
    }

    public static double GetWholeNumber(int[] arrayNumber)
    {
        double result = 0;
        double multiplier = 0;
        var length = arrayNumber.Count() - 1;
        for(int i = 0; i < arrayNumber.Count(); i++)
        {
            multiplier = Math.Pow(10.0, Convert.ToDouble(length));
            result += (arrayNumber[i] * multiplier);
            length = length - 1;
        }

        return result;
    }
}

Sehr einfache Implementierung mit Javascript, nächsthöhere Zahl mit gleichen Ziffern

/*
Algorithm applied
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.

III) Swap the above found two digits, we get 536974 in above example.

IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.

*/

function findNext(arr)
{
  let i;
  //breaking down a digit into arrays of string and then converting back that array to number array
  let arr1=arr.toString().split('').map(Number) ;
  //started to loop from the end of array 
  for(i=arr1.length;i>0;i--)
  {
    //looking for if the current number is greater than the number next to it
    if(arr1[i]>arr1[i-1])
    {// if yes then we break the loop it so that we can swap and sort
      break;}
  }

  if(i==0)
  {console.log("Not possible");}

   else
  {
   //saving that big number and smaller number to the left of it
   let smlNum =arr1[i-1];
    let bigNum =i;
   /*now looping again and checking if we have any other greater number, if we have one AFTER big number and smaller number to the right. 
     A greater number that is of course greater than that smaller number but smaller than the first number we found.
     Why are doing this? Because that is an algorithm to find next higher number with same digits. 
   */
    for(let j=i+1;j<arr1.length;j++)
      {//What if there are no digits afters those found numbers then of course loop will not be initiated otherwise...
        if(arr1[j]> smlNum && arr1[j]<arr1[i])
        {// we assign that other found number here and replace it with the one we found before
          bigNum=j;

        }
      } //now we are doing swapping of places the small num and big number , 3rd part of alogorithm
    arr1[i-1]=arr1[bigNum];
          arr1[bigNum]=smlNum;
    //returning array 
    //too many functions applied sounds complicated right but no, here is the  trick
    //return arr first then apply each function one by one to see output and then further another func to that output to match your needs
    // so here after swapping , 4th part of alogorithm is to sort the array right after the 1st small num we found
    // to do that first we simple take part of array, we splice it and then we apply sort fucntion, then check output (to check outputs, pls use chrome dev console)
    //and then  simply the rest concat and join to main one digit again.
     return arr1.concat((arr1.splice(i,arr1.length)).sort(function(a, b){return a-b})).join('');



    // Sorry to make it too long but its fun explaining things in much easier ways as much as possible!!
  }

}


findNext(1234);

Da es viele Kommentare gibt, ist es besser, sie in Ihren Texteditor zu kopieren. Vielen Dank!

Es gibt viele gute Antworten, aber ich habe keine anständige Java-Implementierung gefunden. Hier sind meine zwei Cent:

public void findNext(int[] nums) {
    int i = nums.length - 1;
    // nums[i - 1] will be the first non increasing number
    while (i > 0 && nums[i] <= nums[i - 1]) {
        i--;
    }
    if (i == 0) {
        System.out.println("it has been the greatest already");
    } else {
        // Find the smallest digit in the second sequence that is larger than it:
        int j = nums.length - 1;
        while (j >= 0 && nums[j] < nums[i - 1]) {
            j--;
        }
        swap(nums, i - 1, j);
        Arrays.sort(nums, i, nums.length);
        System.out.println(Arrays.toString(nums));
    }
}

public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<string.h>
#include<sstream>
#include<iostream>

using namespace std;
int compare (const void * a, const void * b)
{
    return *(char*)a-*(char*)b;
}

/*-----------------------------------------------*/

int main()
{
    char number[200],temp;
    cout<<"please enter your number?"<<endl;
    gets(number);
    int n=strlen(number),length;
    length=n;
    while(--n>0)
    {
        if(number[n-1]<number[n])
        {
            for(int i=length-1;i>=n;i--)
            {
                if(number[i]>number[n-1])
                {
                    temp=number[i];
                    number[i]=number[n-1];
                    number[n-1]=temp;
                    break;
                }
            }
            qsort(number+n,length-n,sizeof(char),compare);
            puts(number); 
            return 0;
        }
    }
    cout<<"sorry itz the greatest one :)"<<endl;
}