Étant donné un nombre, recherchez le nombre immédiatement supérieur qui a exactement le même ensemble de chiffres que le numéro d'origine

Je viens de bombarder une interview et de n'avoir fait pratiquement aucun progrès sur ma question d'entrevue. Quelqu'un peut-il me dire comment procéder? J'ai essayé de chercher en ligne mais je n'ai rien trouvé:

Étant donné un nombre, recherchez le nombre immédiatement supérieur qui a exactement le même ensemble de chiffres que le numéro d'origine. Par exemple: étant donné 38276, renvoyer 38627

Je voulais commencer par trouver l'indice du premier chiffre (à partir de la droite) qui était inférieur à celui des chiffres. Ensuite, je faisais pivoter les derniers chiffres du sous-ensemble de sorte que ce soit le deuxième plus grand nombre composé des mêmes chiffres, mais je suis resté bloqué.

L'intervieweur a également suggéré d'essayer de permuter les chiffres un à la fois, mais je n'ai pas pu comprendre l'algorithme et j'ai juste regardé un écran pendant 20 à 30 minutes. Inutile de dire que je pense que je vais devoir continuer la recherche d'emploi.

edit: pour ce que ça vaut, j'ai été invité à la prochaine série d'entretiens

Vous pouvez le faire en O(n)(où nest le nombre de chiffres) comme ceci:

En partant de la droite, vous trouvez la première paire de chiffres telle que le chiffre de gauche est plus petit que le chiffre de droite. Faisons référence au chiffre de gauche par "digit-x". Trouvez le plus petit nombre supérieur à digit-x à droite de digit-x et placez-le immédiatement à gauche de digit-x. Enfin, triez les chiffres restants dans l'ordre croissant - car ils étaient déjà dans l' ordre décroissant , tout ce que vous avez à faire est de les inverser (sauf pour digit-x, qui peut être placé au bon endroit dans O(n)) .

Un exemple rendra cela plus clair:

123456784987654321
commencer par un nombre

123456784 987654321
         ^ la première place à partir de la droite où le chiffre de gauche est inférieur à la droite  
         Le chiffre "x" est 4

123456784 987654321
              ^ trouver le plus petit chiffre supérieur à 4 à droite

123456785 4 98764321
        ^ placez-le à gauche de 4

123456785 4 12346789
123456785123446789
         ^ triez les chiffres à droite de 5. Puisque tous sauf 
         les «4» étaient déjà en ordre décroissant, tout ce que nous devons faire est 
         inversez leur ordre et trouvez le bon endroit pour le '4'

Preuve de correction:

Utilisons les majuscules pour définir les chaînes de chiffres et les minuscules pour les chiffres. La syntaxe ABsignifie "la concaténation des chaînes Aet B" . <est un ordre lexicographique, qui est identique à un ordre entier lorsque les chaînes de chiffres sont de longueur égale.

Notre numéro d'origine N est de la forme AxB, où xest un seul chiffre et Best trié décroissant.
Le nombre trouvé par notre algorithme est AyC, où y ∈ Best le plus petit chiffre > x (il doit exister en raison de la manière xchoisie, voir ci-dessus) , et Cest trié croissant.

Supposons qu'il existe un certain nombre (en utilisant les mêmes chiffres) N'tel que AxB < N' < AyC. N'doit commencer par Aou sinon il ne pourrait pas tomber entre eux, donc nous pouvons l'écrire dans le formulaire AzD. Maintenant, notre inégalité est AxB < AzD < AyC, ce qui équivaut à l' xB < zD < yCendroit où les trois chaînes de chiffres contiennent les mêmes chiffres.

Pour que cela soit vrai, nous devons avoir x <= z <= y. Puisque yc'est le plus petit chiffre > x, zne peut pas être entre eux, donc soit z = xou z = y. Dis z = x. Ensuite, notre inégalité est xB < xD < yC, ce qui signifie B < Doù les deux Bet Dont les mêmes chiffres. Cependant, B est trié décroissant, il n'y a donc pas de chaîne avec ces chiffres plus grands que lui. Nous ne pouvons donc pas avoir B < D. En suivant les mêmes étapes, nous voyons que si z = y, nous ne pouvons pas avoir D < C.

Par conséquent, N'il ne peut pas exister, ce qui signifie que notre algorithme trouve correctement le prochain plus grand nombre.

Un problème presque identique est apparu comme un problème Code Jam et a une solution ici:

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

Voici un résumé de la méthode à l'aide d'un exemple:

34722641

A. Divisez la séquence de chiffres en deux afin que la partie droite soit aussi longue que possible tout en restant dans l'ordre décroissant:

34722 641

(Si le nombre entier est en ordre décroissant, il n'y a pas de plus grand nombre à faire sans ajouter de chiffres.)

B.1. Sélectionnez le dernier chiffre de la première séquence:

3472(2) 641

B.2. Trouvez le plus petit chiffre de la deuxième séquence qui est plus grand que lui:

3472(2) 6(4)1

B.3. Échangez-les:

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

C. Triez la deuxième séquence par ordre croissant:

34724 126

D. Terminé!

34724126

Voici une solution compacte (mais en partie brutale) en Python

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

En C ++, vous pouvez faire les permutations comme ceci: https://stackoverflow.com/a/9243091/1149664 (C'est le même algorithme que celui dans itertools)

Voici une implémentation de la première réponse décrite par Weeble et BlueRaja, (autres réponses). Je doute qu'il y ait quelque chose de mieux.

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)))))

Au minimum, voici quelques exemples de solutions basées sur des chaînes de force brute, que vous auriez dû être en mesure de trouver dès le départ:

la liste des chiffres 38276triés est23678

la liste des chiffres 38627triés est23678

incrémenter, trier et comparer la force brute

Le long de la force brute, les solutions seraient converties en une chaîne et en force brute tous les nombres possibles en utilisant ces chiffres.

Créez des entiers à partir de tous, mettez-les dans une liste et triez-les, obtenez l'entrée suivante après l'entrée cible.

Si vous avez passé 30 minutes sur ce sujet et n'avez pas au moins trouvé au moins une approche par force brute, je ne vous embaucherais pas non plus.

Dans le monde des affaires, une solution inélégante, lente et maladroite mais qui fait le travail a toujours plus de valeur qu'aucune solution, en fait, elle décrit à peu près tous les logiciels d'entreprise, inélégants, lents et maladroits.

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

Ton idée

Je voulais commencer par trouver l'indice du premier chiffre (à partir de la droite) qui était inférieur à celui des chiffres. Ensuite, je faisais pivoter les derniers chiffres du sous-ensemble de sorte que ce soit le deuxième plus grand nombre composé des mêmes chiffres, mais je suis resté bloqué.

est assez bon, en fait. Il vous suffit de prendre en compte non seulement le dernier chiffre, mais tous les chiffres de moindre importance que celui actuellement considéré. Depuis avant cela, nous avons une séquence monotone de chiffres, c'est-à-dire le chiffre le plus à droite plus petit que son voisin droit. Qui concerne

1234675
    ^

Le nombre supérieur suivant ayant les mêmes chiffres est

1234756

Le chiffre trouvé est échangé contre le dernier chiffre - le plus petit des chiffres considérés - et les chiffres restants sont classés par ordre croissant.

Je suis assez sûr que votre intervieweur essayait de vous pousser doucement vers quelque chose comme ça:

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);

Pas nécessairement la solution la plus efficace ou la plus élégante, mais elle résout l'exemple fourni en deux cycles et permute les chiffres un à la fois comme il l'a suggéré.

Prenez un nombre et divisez-le en chiffres. Donc, si nous avons un nombre à 5 chiffres, nous avons 5 chiffres: abcde

Maintenant, échangez d et e et comparez avec le nombre d'origine, s'il est plus grand, vous avez votre réponse.

S'il n'est pas plus grand, échangez e et c. Maintenant, comparez et s'il est plus petit, échangez à nouveau d et e (remarquez la récursivité), prenez le plus petit.

Continuez jusqu'à ce que vous trouviez un plus grand nombre. Avec la récursivité, cela devrait fonctionner comme environ 9 lignes de schéma, ou 20 de c #.

C'est une question très intéressante.

Voici ma version java. Prenez-moi environ 3 heures après avoir trouvé le modèle pour terminer complètement le code avant de vérifier les commentaires des autres contributeurs. Heureux de voir que mon idée est la même que celle des autres.

Solution O (n). Honnêtement, j'échouerai cette interview si le temps n'est que de 15 minutes et nécessite la fin du code complet sur tableau blanc.

Voici quelques points intéressants pour ma solution:

• Evitez tout tri.
• Évitez complètement le fonctionnement des chaînes
• Atteindre la complexité de l'espace O (logN)

Je mets des commentaires détaillés dans mon code, et le Big O à chaque étape.

  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;

}

Voici le résultat en cours d'exécution dans Intellj:

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

Une implémentation javascript de l'algorithme de @ BlueRaja.

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;
};

Une solution (en Java) pourrait être la suivante (je suis sûr que des amis ici peuvent trouver une meilleure solution):
Commencez à échanger des chiffres à partir de la fin de la chaîne jusqu'à ce que vous obteniez un nombre plus élevé.
C'est-à-dire commencer d'abord à monter le chiffre inférieur, puis le prochain supérieur, etc. jusqu'à ce que vous atteigniez le prochain supérieur.
Triez ensuite le reste. Dans votre exemple, vous obtiendrez:

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));
}

Si vous programmez en C ++, vous pouvez utiliser 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;
}

Je ne savais rien de l'algorithme de force brute en répondant à cette question, alors je l'ai abordé sous un autre angle. J'ai décidé de rechercher toute la gamme de solutions possibles dans lesquelles ce nombre pourrait éventuellement être réorganisé, en commençant par number_given + 1 jusqu'au nombre maximum disponible (999 pour un nombre à 3 chiffres, 9999 pour 4 chiffres, etc.). J'ai fait ce genre de recherche d'un palindrome avec des mots, en triant les nombres de chaque solution et en les comparant au nombre trié donné comme paramètre. J'ai ensuite simplement renvoyé la première solution dans le tableau de solutions, car ce serait la prochaine valeur possible.

Voici mon code en 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

Code PHP

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);

Je n'ai testé cela qu'avec deux chiffres. Ils ont travaillé. En tant que responsable informatique pendant 8 ans jusqu'à ma retraite en décembre dernier, je me souciais de trois choses: 1) Précision: c'est bien si cela fonctionne - toujours. 2) Vitesse: doit être acceptable pour l'utilisateur. 3) Clarté: je ne suis probablement pas aussi intelligent que vous, mais je vous paie. Assurez-vous d'expliquer ce que vous faites, en anglais.

Omar, bonne chance pour l'avenir.

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

Pour une belle description de la façon de procéder, voir « Algorithme L » dans « L'art de la programmation informatique: générer toutes les permutations » de Knuth (.ps.gz).

Voici mon code, c'est une version modifiée de cet exemple

Bibliothèque:

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;
    }
}

Tester:

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

    int b = NumPermExample.nextPermutation(a);

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

Ajoutez 9 au nombre de n chiffres donné. Vérifiez ensuite s'il se trouve dans la limite (le premier (n + 1) chiffre). Si c'est le cas, vérifiez si les chiffres du nouveau numéro sont identiques à ceux du numéro d'origine. Répétez l'ajout de 9 jusqu'à ce que les deux conditions soient remplies. Arrêtez l'algo lorsque le nombre dépasse la limite.

Je n'ai pas pu trouver un cas de test contradictoire pour cette méthode.

Juste une autre solution utilisant 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)

Production:

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);
        }

    }

Ci-dessous se trouve le code pour générer toutes les permutations d'un nombre .. bien qu'il faut d'abord convertir cet entier en chaîne en utilisant String.valueOf (entier).

/**
 * 
 * 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;
}

Encore une autre implémentation Java, exécutable prête à l'emploi et complétée par des tests. Cette solution est O (n) espace et temps en utilisant une bonne vieille programmation dynamique.

Si l'on veut brutaliser, il existe 2 types de bruteforce:

1. Permutez toutes les choses, puis choisissez min plus haut: O (n!)

2. Similaire à cette implémentation, mais au lieu de DP, l'application brute de l'étape de remplissage de la carte indexToIndexOfNextSmallerLeft s'exécutera dans O (n ^ 2).

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);
    }

}

Nous devons trouver le bit 0 le plus à droite suivi d'un 1 et retourner ce bit le plus à droite en 1.

par exemple, disons que notre entrée est 487, qui est 111100111 en binaire.

nous retournons le plus à droite 0 qui a 1 suivant

nous obtenons donc 111101111

mais maintenant nous avons un 1 supplémentaire et un 0 de moins, donc nous réduisons le nombre de 1 à droite du bit flip de 1 et augmentons le nombre de 0 bits de 1, ce qui donne

111101011 - binaire 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");
}

Voici l'implémentation Java

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;
}

Voici les tests unitaires

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

Je sais que c'est une très vieille question mais je n'ai toujours pas trouvé de code facile en c #. Cela pourrait aider les gars qui assistent aux entretiens.

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;
    }
}

Implémentation très simple en utilisant Javascript, numéro suivant avec les mêmes chiffres

/*
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);

Comme il y a beaucoup de commentaires, il est préférable de le copier dans votre éditeur de texte. Merci!

Il y a beaucoup de bonnes réponses mais je n'ai pas trouvé d'implémentation Java décente. Voici mes deux cents:

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;
}