Biorąc pod uwagę liczbę, znajdź następny wyższy numer, który ma dokładnie taki sam zestaw cyfr jak numer oryginalny

Właśnie zbombardowałem wywiad i zrobiłem prawie zerowy postęp w kwestii mojego pytania. Czy ktoś może mi powiedzieć, jak to zrobić? Próbowałem wyszukać w Internecie, ale nic nie znalazłem:

Biorąc pod uwagę liczbę, znajdź następny wyższy numer, który ma dokładnie taki sam zestaw cyfr jak numer oryginalny. Na przykład: dane 38276 zwracają 38627

Chciałem zacząć od znalezienia indeksu pierwszej cyfry (od prawej), który był mniejszy niż cyfra jedynek. Następnie obracałbym ostatnie cyfry podzbioru, tak aby była to kolejna największa liczba złożona z tych samych cyfr, ale utknęła.

Ankieter zasugerował również próbę zamiany cyfr pojedynczo, ale nie mogłem rozgryźć algorytmu i po prostu wpatrywałem się w ekran przez około 20-30 minut. Nie trzeba dodawać, że myślę, że będę musiał kontynuować poszukiwanie pracy.

edytuj: za jaką wartość, zostałem zaproszony do następnej rundy wywiadów

Możesz to zrobić w O(n)(gdzie njest liczba cyfr) w następujący sposób:

Zaczynając od prawej, znajdziesz pierwszą parę cyfr, dzięki czemu lewa cyfra jest mniejsza niż prawa cyfra. Odwołajmy się do lewej cyfry przez „digit-x”. Znajdź najmniejszą liczbę większą niż cyfra-x na prawo od cyfry-x i umieść ją bezpośrednio na lewo od cyfry-x. Na koniec posortuj pozostałe cyfry w porządku rosnącym - ponieważ były one już w kolejności malejącej , wystarczy je odwrócić (z wyjątkiem cyfry-x, którą można umieścić we właściwym miejscu O(n)) .

Przykład wyjaśni to:

123456784987654321
zacznij od liczby

123456784 987654321
         ^ pierwsze miejsce z prawej strony, w którym lewa cyfra jest mniejsza niż prawa  
         Cyfra „x” to 4

123456784 987654321
              ^ znajdź najmniejszą cyfrę większą niż 4 po prawej stronie

123456785 4 98764321
        ^ umieść go na lewo od 4

123456785 4 12346789
123456785123446789
         ^ posortuj cyfry po prawej stronie 5. Ponieważ wszystkie oprócz 
         „4” były już w porządku malejącym, wszystko, co musimy zrobić, to 
         odwróć ich kolejność i znajdź właściwe miejsce dla „4”

Dowód poprawności:

Użyjmy wielkich liter, aby zdefiniować ciągi znaków i małe litery dla cyfr. Składnia ABoznacza „łączenie łańcuchów Ai B” . <to uporządkowanie leksykograficzne, które jest takie samo jak uporządkowanie liczb całkowitych, gdy ciągi cyfr są równej długości.

Nasz oryginalny numer N ma postać AxB, gdzie xjest pojedynczą cyfrą i Bjest posortowany malejąco.
Liczba znaleziona przez nasz algorytm to AyC, gdzie y ∈ Bjest najmniejsza cyfra > x (musi istnieć z powodu wybranego sposobu x, patrz wyżej) i Cjest posortowana rosnąco.

Załóżmy, że istnieje pewna liczba (przy użyciu tych samych cyfr), N'taka jak AxB < N' < AyC. N'musi zaczynać się od tego, Ainaczej nie może się między nimi znaleźć, więc możemy napisać to w formie AzD. Teraz nasza nierówność jest AxB < AzD < AyCrówna, gdy xB < zD < yCwszystkie trzy ciągi cyfr zawierają te same cyfry.

Aby było to prawdą, musimy to zrobić x <= z <= y. Ponieważ yjest najmniejsza cyfra > x, znie może być między nimi, więc albo z = xalbo z = y. Powiedzmy z = x. Wtedy nasza nierówność jest xB < xD < yC, co oznacza, B < Dgdzie zarówno Bi Dmają takie same cyfry. Jednakże, B jest posortowana malejąco, więc nie jest żaden ciąg cyfr z tych większych od niego. Dlatego nie możemy mieć B < D. Po tych samych krokach widzimy, że jeśli z = ynie możemy D < C.

Dlatego N'nie może istnieć, co oznacza, że ​​nasz algorytm poprawnie znajduje następną największą liczbę.

Prawie identyczny problem pojawił się jako problem z zacięciem kodu i ma rozwiązanie tutaj:

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

Oto podsumowanie metody na przykładzie:

34722641

A. Podziel sekwencję cyfr na dwie części, aby prawa część była jak najdłuższa, pozostając w malejącej kolejności:

34722 641

(Jeśli cały numer jest w malejącej kolejności, nie ma większej liczby do zrobienia bez dodania cyfr).

B.1 Wybierz ostatnią cyfrę pierwszej sekwencji:

3472(2) 641

B.2 Znajdź najmniejszą cyfrę w drugiej sekwencji, która jest większa:

3472(2) 6(4)1

B.3 Zamień je:

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

C. Posortuj drugą sekwencję w kolejności rosnącej:

34724 126

D. Gotowe!

34724126

Oto kompaktowe (ale częściowo brutalne) rozwiązanie w Pythonie

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

W C ++ możesz dokonać takich permutacji: https://stackoverflow.com/a/9243091/1149664 (To ten sam algorytm jak w itertools)

Oto implementacja najważniejszej odpowiedzi opisanej przez Weeble i BlueRaja (inne odpowiedzi). Wątpię, żeby było coś lepszego.

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

Oto kilka przykładowych rozwiązań opartych na łańcuchach siłowych, które powinieneś być w stanie wymyślić od razu:

lista 38276posortowanych cyfr to23678

lista 38627posortowanych cyfr to23678

przyrost siły brutalnej, sortowanie i porównywanie

Wzdłuż brutalnej siły rozwiązania byłyby konwertowane na ciąg i brutalną siłę wszystkich możliwych liczb za pomocą tych cyfr.

Utwórz ints z nich wszystkich, umieść je na liście i posortuj, uzyskaj następny wpis po wpisie docelowym.

Jeśli spędziłeś na tym 30 minut i przynajmniej nie wymyśliłeś przynajmniej brutalnej siły, ja też cię nie zatrudniłbym.

W świecie biznesu rozwiązanie, które jest nieeleganckie, powolne i niezgrabne, ale umożliwia wykonanie zadania, jest zawsze bardziej wartościowe niż żadne rozwiązanie, fakt, że w zasadzie opisuje całe oprogramowanie biznesowe, nieeleganckie, powolne i niezgrabne.

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

Twój pomysł

Chciałem zacząć od znalezienia indeksu pierwszej cyfry (od prawej), który był mniejszy niż cyfra jedynek. Następnie obracałbym ostatnie cyfry podzbioru, tak aby była to kolejna największa liczba złożona z tych samych cyfr, ale utknęła.

jest całkiem niezła. Musisz wziąć pod uwagę nie tylko ostatnią cyfrę, ale wszystkie cyfry o mniejszym znaczeniu niż obecnie rozważane. Ponieważ zanim to zostanie osiągnięte, mamy monotoniczną sekwencję cyfr, która jest skrajną prawą cyfrą mniejszą niż jej prawy sąsiad. Wzgląd

1234675
    ^

Kolejny większy numer mający te same cyfry to

1234756

Znaleziona cyfra jest wymieniana na ostatnią cyfrę - najmniejszą z rozpatrywanych cyfr - a pozostałe cyfry są ułożone w kolejności rosnącej.

Jestem całkiem pewien, że twój ankieter próbował delikatnie popchnąć cię do czegoś takiego:

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

Niekoniecznie najbardziej wydajne lub eleganckie rozwiązanie, ale rozwiązuje podany przykład w dwóch cyklach i zamienia cyfry po jednym, tak jak sugerował.

Weź liczbę i podziel ją na cyfry. Więc jeśli mamy 5-cyfrowy numer, mamy 5 cyfr: abcde

Teraz zamień d i e i porównaj z oryginalnym numerem, jeśli jest większy, masz swoją odpowiedź.

Jeśli nie jest większy, zamień e i c. Teraz porównaj, a jeśli jest mniejszy, zamień d i e ponownie (zauważ rekurencję), weź najmniejszy.

Kontynuuj, aż znajdziesz większą liczbę. Z rekurencją powinno działać jako około 9 linii schematu lub 20 c #.

To bardzo interesujące pytanie.

Oto moja wersja Java. Poświęć mi około 3 godzin od wymyślenia wzoru, aby całkowicie ukończyć kod, zanim sprawdzę komentarze innych autorów. Cieszę się, że mój pomysł jest taki sam z innymi.

Roztwór O (n). Szczerze mówiąc, nie uda mi się przeprowadzić tego wywiadu, jeśli będzie to tylko 15 minut i będę wymagał pełnego zakończenia kodu na białej tablicy.

Oto kilka interesujących punktów dla mojego rozwiązania:

• Unikaj sortowania.
• Całkowicie unikaj operacji na łańcuchach
• Osiągnij złożoność przestrzeni O (logN)

W każdym kodzie umieszczam szczegółowy komentarz i Big O na każdym kroku.

  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;

}

Oto wynik działający w Intellj:

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

Implementacja javascript algorytmu @ 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;
};

Rozwiązanie (w Javie) może wyglądać następująco (jestem pewien, że przyjaciele tutaj mogą znaleźć coś lepszego):
Zacznij zamieniać cyfry od końca łańcucha, aż uzyskasz wyższą liczbę.
Tzn. Najpierw zacznij przesuwać się w górę o niższą cyfrę, a następnie następny wyższy itp., Aż dojdziesz do następnej wyższej.
Następnie posortuj resztę. W twoim przykładzie otrzymasz:

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

Jeśli programujesz w C ++, możesz użyć 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;
}

Odpowiadając na to pytanie, nie wiedziałem nic o algorytmie brutalnej siły, więc podszedłem do niego z innej perspektywy. Postanowiłem poszukać całej gamy możliwych rozwiązań, na które można zmienić tę liczbę, zaczynając od podanej liczby + 1 aż do maksymalnej dostępnej liczby (999 dla liczby 3-cyfrowej, 9999 dla 4 cyfr itp.). Zrobiłem coś w rodzaju znalezienia palindromu ze słowami, sortując liczby każdego rozwiązania i porównując je z posortowaną liczbą podaną jako parametr. Następnie po prostu zwróciłem pierwsze rozwiązanie z szeregu rozwiązań, ponieważ byłaby to kolejna możliwa wartość.

Oto mój kod w 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

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

Testowałem to tylko z dwiema liczbami. Oni pracowali. Jako kierownik działu IT przez 8 lat, aż do przejścia na emeryturę w grudniu ubiegłego roku, zależało mi na trzech rzeczach: 1) Dokładność: dobrze, jeśli działa - zawsze. 2) Prędkość: musi być do zaakceptowania przez użytkownika. 3) Jasność: Prawdopodobnie nie jestem tak mądry jak ty, ale płacę ci. Wyjaśnij po angielsku, co robisz.

Omar, powodzenia.

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

Aby dowiedzieć się, jak to zrobić, zobacz „ Algorytm L ” w „ Sztuce programowania komputerowego Knutha : generowanie wszystkich permutacji ” (.ps.gz).

Oto mój kod, to zmodyfikowana wersja tego przykładu

Biblioteka:

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

Test:

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

    int b = NumPermExample.nextPermutation(a);

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

Dodaj 9 do podanej liczby n cyfr. Następnie sprawdź, czy mieści się w limicie (pierwsza (n + 1) cyfra). Jeśli tak, sprawdź, czy cyfry w nowym numerze są takie same jak cyfry w oryginalnym numerze. Powtarzaj dodawanie 9, dopóki oba warunki nie będą spełnione. Zatrzymaj algo, gdy liczba przekroczy limit.

Nie mogłem wymyślić sprzecznego przypadku testowego dla tej metody.

Kolejne rozwiązanie wykorzystujące 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)

Wynik:

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

    }

Poniżej znajduje się kod do generowania wszystkich permutacji liczby .. chociaż najpierw trzeba przekonwertować tę liczbę całkowitą na ciąg, używając String.valueOf (liczba całkowita).

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

Kolejna implementacja Java, którą można uruchomić po wyjęciu z pudełka i zakończyć testami. Rozwiązaniem jest O (n) przestrzeń i czas przy użyciu starego dobrego programowania dynamicznego.

Jeśli ktoś chce użyć siły, istnieją 2 rodzaje siły:

1. Zezwól na wszystkie rzeczy, a następnie wybierz min wyżej: O (n!)

2. Podobnie do tej implementacji, ale zamiast DP, brutalne wykonanie kroku wypełniania mapy indexToIndexOfNextSmallerLeft będzie działało w 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);
    }

}

Musimy znaleźć najbardziej prawy bit 0, a następnie 1 i odwrócić ten najbardziej z prawej 0 bit na 1.

na przykład powiedzmy, że nasze dane wejściowe to 487, czyli dwójka 111100111.

odwracamy w prawo najbardziej 0, która ma 1 po nim

więc otrzymujemy 111101111

ale teraz mamy dodatkowe 1 i jeden mniej 0, więc zmniejszamy liczbę 1 po prawej stronie bitu flip o 1 i zwiększamy liczbę 0 bitów o 1, uzyskując

111101011 - dwójkowy 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");
}

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

Oto testy jednostkowe

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

Wiem, że to bardzo stare pytanie, ale wciąż nie znalazłem łatwego kodu w c #. Może to pomóc facetom, którzy biorą udział w wywiadach.

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

Bardzo prosta implementacja przy użyciu Javascript, następny najwyższy numer z tymi samymi cyframi

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

Ponieważ jest wiele komentarzy, więc lepiej skopiować go do edytora tekstu. Dzięki!

Istnieje wiele dobrych odpowiedzi, ale nie znalazłem przyzwoitej implementacji Java. Oto moje dwa centy:

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