По заданному номеру найдите следующее более высокое число, которое имеет тот же набор цифр, что и исходное число.

Я просто разбомбил интервью и почти не продвинулся в вопросе об интервью. Кто-нибудь может дать мне знать, как это сделать? Я пытался искать в Интернете, но ничего не смог найти:

По заданному номеру найдите следующее более высокое число, которое имеет тот же набор цифр, что и исходное число. Например: дано 38276, возвращено 38627

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

Интервьюер также предложил попробовать поменять цифры по одной за раз, но я не мог понять алгоритм и просто смотрел на экран в течение 20-30 минут. Само собой разумеется, я думаю, что мне придется продолжить поиски работы.

редактировать: для чего он стоит, меня пригласили на следующий раунд интервью

Вы можете сделать это в O(n)(где nчисло цифр) следующим образом:

Начиная справа, вы найдете первую пару цифр, такую, что левая цифра будет меньше правой цифры. Давайте обратимся к левой цифре "цифра-х". Найдите наименьшее число больше цифры-x справа от цифры-x и поместите его сразу слева от цифры-x. Наконец, сортируйте оставшиеся цифры в порядке возрастания - поскольку они уже были в порядке убывания, все, что вам нужно сделать, это перевернуть их (за исключением цифры-x, которая может быть размещена в правильном месте в O(n)) .

Пример прояснит это:

123456784987654321
начать с числа

123456784 987654321
         ^ первое место справа, где левая цифра меньше правой  
         Цифра "х" 4

123456784 987654321
              ^ найдите самую маленькую цифру больше 4 справа

123456785 4 98764321
        ^ поместите это слева от 4

123456785 4 12346789
123456785123446789
         ^ Сортируйте цифры справа от 5. Так как все они, кроме 
         «4» были уже в порядке убывания, все, что нам нужно сделать, это 
         измените их порядок и найдите правильное место для «4»

Доказательство правильности:

Давайте использовать заглавные буквы для определения цифр-строк и строчные буквы для цифр. Синтаксис ABозначает «объединение строк Aи B» . <это лексикографический порядок, который совпадает с целочисленным порядком, когда строки цифр имеют одинаковую длину.

Наш оригинальный номер N имеет форму AxB, где xэто одна цифра и Bсортируется по убыванию.
Число, найденное нашим алгоритмом, - это AyCгде y ∈ Bнаименьшая цифра > x (она должна существовать в зависимости от xвыбранного пути , см. Выше) и Cсортируется по возрастанию.

Предположим, что есть какое-то число (с использованием тех же цифр) N', что AxB < N' < AyC. N'должен начинаться с, Aиначе он не может попасть между ними, поэтому мы можем записать это в форме AzD. Теперь наше неравенство AxB < AzD < AyCравнозначно тому, что xB < zD < yCвсе три строки цифр содержат одинаковые цифры.

Для того чтобы это было правдой, мы должны иметь x <= z <= y. Поскольку yэто самая маленькая цифра > x, zне может быть между ними, так что либо z = xили z = y. Say z = x. Тогда наше неравенство есть xB < xD < yC, что означает, B < Dгде оба Bи Dимеют одинаковые цифры. Однако, В отсортированный по убыванию, так что не не строка с этих цифр больше , чем это. Таким образом, мы не можем иметь B < D. Следуя тем же шагам, мы видим, что если z = yне можем D < C.

Следовательно, N'не может существовать, что означает, что наш алгоритм правильно находит следующее наибольшее число.

Почти идентичная проблема появилась как проблема Code Jam и имеет решение здесь:

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

Вот краткое описание метода на примере:

34722641

A. Разделите последовательность цифр на две части, чтобы правая часть была максимально длинной, оставаясь в порядке убывания:

34722 641

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

B.1. Выберите последнюю цифру первой последовательности:

3472(2) 641

БИ 2. Найдите наименьшую цифру во второй последовательности, которая больше ее:

3472(2) 6(4)1

В.3. Поменяйте их местами:

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

C. Сортировка второй последовательности в порядке возрастания:

34724 126

D. Готово!

34724126

Вот компактное (но частично грубое) решение в Python

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

В C ++ вы можете сделать перестановки следующим образом: https://stackoverflow.com/a/9243091/1149664 (это тот же алгоритм, что и в itertools)

Вот реализация верхнего ответа, описанного Weeble и BlueRaja (другие ответы). Я сомневаюсь, что есть что-то лучше.

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

Как минимум, вот пара примеров решений на основе грубой силы на основе String, которые вы должны были бы придумать прямо из головы:

список цифр в 38276отсортированном23678

список цифр в 38627отсортированном23678

Приращение грубой силы, сортировка и сравнение

Вдоль решений грубой силы будут преобразованы в строку и перебор всех возможных чисел с использованием этих цифр.

Создайте целые из них, поместите их в список и отсортируйте, получив следующую запись после целевой записи.

Если бы вы потратили на это 30 минут и, по крайней мере, не придумали хотя бы грубого подхода, я бы вас тоже не нанял.

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

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

Твоя идея

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

довольно хорошо, на самом деле. Вам просто нужно учитывать не только последнюю цифру, но и все цифры менее значимые, чем рассматриваемые в настоящее время. Поскольку до этого мы имеем монотонную последовательность цифр, то есть крайняя правая цифра меньше, чем ее правая соседка. Рассматривать

1234675
    ^

Следующее большее число, имеющее те же цифры

1234756

Найденная цифра заменяется на последнюю цифру - наименьшую из рассмотренных цифр, а остальные цифры располагаются в порядке возрастания.

Я вполне уверен, что ваш интервьюер пытался мягко подтолкнуть вас к чему-то вроде этого:

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

Не обязательно самое эффективное или элегантное решение, но оно решает предоставленный пример в два цикла и меняет цифры по одному, как он предложил.

Возьмите число и разбейте его на цифры. Так что, если у нас есть 5-значное число, у нас есть 5 цифр: abcde

Теперь поменяйте местами d и e и сравните с исходным числом, если оно больше, у вас есть ответ.

Если он не больше, поменяйте местами e и c. Теперь сравните и, если оно меньше, поменяйте местами d и e снова (обратите внимание на рекурсию), возьмите наименьшее.

Продолжайте, пока не найдете большее число. С рекурсией это должно работать примерно как 9 строк схемы или 20 из c #.

Это очень интересный вопрос.

Вот моя версия Java. У меня уйдет около 3 часов от выяснения шаблона до полного завершения кода, прежде чем я проверю комментарии других участников. Рад, что моя идея совершенно такая же, как и у других.

O (n) решение. Честно говоря, я не смогу пройти это собеседование, если на это уйдет всего 15 минут и мне понадобится закончить код на белой доске.

Вот несколько моментов, интересных для моего решения:

• Избегайте любой сортировки.
• Избегайте строковых операций полностью
• Добиться O (logN) пространственной сложности

Я добавляю подробный комментарий в мой код и Big O на каждом шаге.

  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;

}

Вот результат работы в Intellj:

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

Реализация javascript алгоритма @ 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;
};

Решение (на Java) может быть следующим (я уверен, что друзья здесь могут найти лучшее):
начинайте поменять цифры с конца строки, пока не получите большее число.
Т.е. сначала начинайте двигаться вверх по нижней цифре. Затем по следующей более высокой и т.д.
Тогда сортируй остальное. В вашем примере вы получите:

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

Если вы программируете на C ++, вы можете использовать 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;
}

При ответе на этот вопрос я ничего не знал об алгоритме грубой силы, поэтому подошел к нему с другой стороны. Я решил поискать весь спектр возможных решений, в которые можно переставить это число, начиная с number_given + 1 до максимального доступного числа (999 для трехзначного числа, 9999 для четырехзначного и т. Д.). Я сделал подобный поиск палиндрома со словами, отсортировав номера каждого решения и сравнив его с отсортированным числом, указанным в качестве параметра. Затем я просто вернул первое решение в массиве решений, так как это было бы следующим возможным значением.

Вот мой код в 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

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

Я проверил это только с двумя числами. Они работали. Работая IT-менеджером в течение 8 лет до ухода на пенсию в декабре прошлого года, я заботился о трех вещах: 1) Точность: хорошо, если это работает - всегда. 2) Скорость: должна быть приемлемой для пользователя. 3) Ясность: я, наверное, не такой умный, как ты, но я тебе плачу. Обязательно объясните, что вы делаете, на английском языке.

Омар, удачи в будущем.

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

Подробное описание того, как это сделать, см. В разделе « Алгоритм L » в книге Кнута « Искусство компьютерного программирования: создание всех перестановок » (.ps.gz).

Вот мой код, это модифицированная версия этого примера

Библиотека:

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

Тест:

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

    int b = NumPermExample.nextPermutation(a);

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

Добавьте 9 к данному n-значному номеру. Затем проверьте, находится ли он в пределах предела (первая (n + 1) цифра). Если это так, проверьте, совпадают ли цифры в новом номере с цифрами в оригинальном номере. Повторите добавление 9, пока оба условия не будут выполнены. Остановите алгоритм, когда число выходит за пределы.

Я не мог придумать противоречивый контрольный пример для этого метода.

Просто еще одно решение с использованием 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)

Вывод:

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

    }

Ниже приведен код для генерации всех перестановок числа ... хотя сначала нужно преобразовать это целое число в строку, используя String.valueOf (integer).

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

Еще одна реализация Java, запускаемая из коробки и дополненная тестами. Это решение O (n) пространства и времени с использованием старого доброго динамического программирования.

Если кто-то хочет брутфорс, есть 2 вида брутфорс:

1. Перестановка всех вещей, затем выберите мин выше: O (n!)

2. Аналогично этой реализации, но вместо DP выполнение шага заполнения карты indexToIndexOfNextSmallerLeft будет выполняться в 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);
    }

}

Нам нужно найти самый правый бит 0, за которым следует 1, и перевернуть этот самый правый бит 0 в 1.

Например, допустим, что наш ввод 487, что в двоичном виде 111100111.

мы переворачиваем самое правое 0, за которым следует 1

поэтому мы получаем 111101111

но теперь у нас есть дополнительный 1 и один меньше 0, поэтому мы уменьшаем число 1 справа от перевёрнутого бита на 1 и увеличиваем число бит 0 на 1, получая

111101011 - двоичный код 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");
}

Вот реализация 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;
}

Вот модульные тесты

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

Я знаю, что это очень старый вопрос, но все же я не нашел простой код в C #. Это может помочь парням, которые посещают интервью.

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

Очень простая реализация с использованием Javascript, следующий по числу с теми же цифрами

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

Поскольку комментариев много, лучше скопировать их в текстовый редактор. Спасибо!

Есть много хороших ответов, но я не нашел достойной реализации Java. Вот мои два цента:

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