给定一个数字，找到下一个更高的数字，它的数字与原始数字完全相同。

I just bombed an interview and made pretty much zero progress on my interview question. Can anyone let me know how to do this? I tried searching online but couldn't find anything:

我刚刚对面试进行了轰炸，在面试问题上几乎毫无进展。有人能告诉我怎么做吗?我试着在网上搜索，但什么也找不到:

Given a number, find the next higher number which has the exact same set of digits as the original number. For example: given 38276 return 38627

给定一个数字，找到下一个更高的数字，它的数字与原始数字完全相同。例如:给定38276返回38627。

I wanted to begin by finding the index of the first digit (from the right) that was less than the ones digit. Then I would rotate the last digits in the subset such that it was the next biggest number comprised of the same digits, but got stuck.

我想先找到小于个位数的第一个数字(从右边)的索引。然后我将最后一个数字在子集里旋转它是下一个最大的数字由相同的数字组成，但是被卡住了。

The interviewer also suggested trying to swap digits one at a time, but I couldn't figure out the algorithm and just stared at a screen for like 20-30 minutes. Needless to say, I think I'm going to have to continue the job hunt.

面试官还建议试着一次换一个数字，但我不能算出算法，只是盯着屏幕看了20-30分钟。不用说，我想我得继续找工作了。

edit: for what its worth, I was invited to the next round of interviews

编辑:为了它的价值，我被邀请参加下一轮面试。

35 个解决方案

#1

You can do it in O(n) (where n is the number of digits) like this:

你可以用O(n)来表示(n是数字的个数)

Starting from the right, you find the first pair-of-digits such that the left-digit is smaller than the right-digit. Let's refer to the left-digit by "digit-x". Find the smallest number larger than digit-x to the right of digit-x, and place it immediately left of digit-x. Finally, sort the remaining digits in ascending order - since they were already in descending order, all you need to do is reverse them (save for digit-x, which can be placed in the correct place in O(n)).

从右边开始，你会发现第一个数字，这样左位数比右位小。让我们用“digit-x”来指代左边的数字。找出比digit-x更小的数字，并把它放在digit-x的右边。最后，按升序对其余的数字进行排序——因为它们已经按降序排列了，您需要做的就是将它们反转(保存为digit-x，可以放置在O(n)的正确位置)。

An example will make this more clear:

一个例子将使这个更加清晰:

123456784987654321
start with a number

123456784 987654321
         ^the first place from the right where the left-digit is less than the right  
         Digit "x" is 4

123456784 987654321
              ^find the smallest digit larger than 4 to the right

123456785 4 98764321
        ^place it to the left of 4

123456785 4 12346789
123456785123446789
         ^sort the digits to the right of 5.  Since all of them except 
         the '4' were already in descending order, all we need to do is 
         reverse their order, and find the correct place for the '4'

---

Proof of correctness:

正确性的证明:

Let's use capital letters to define digit-strings and lower-case for digits. The syntax AB means "the concatenation of strings A and B". < is lexicographical ordering, which is the same as integer ordering when the digit-strings are of equal length.

让我们用大写字母来定义数字字符串和小写字母。语法AB表示“字符串A和B的连接”。 <是词典排序，当数字字符串长度相等时，它与整数排序相同。< p>

Our original number N is of the form AxB, where x is a single digit and B is sorted descending.
The number found by our algorithm is AyC, where y ∈ B is the smallest digit > x (it must exist due to the way x was chosen, see above), and C is sorted ascending.

我们原来的数字N是AxB，其中x是个位数，B是递减的。我们算法发现的数量是美国青年代表大会,y∈B是最小的数字> x(它必须存在由于x被选中,见上图),和C是升序排序。

Assume there is some number (using the same digits) N' such that AxB < N' < AyC. N' must begin with A or else it could not fall between them, so we can write it in the form AzD. Now our inequality is AxB < AzD < AyC, which is equivalent to xB < zD < yC where all three digit-strings contain the same digits.

假设有一些数字(使用相同的数字)，比如AxB < N' < AyC。N'必须从A开始，否则它不能落在它们之间，所以我们可以把它写成AzD的形式。现在我们的不等式是AxB < AzD < AyC，它等价于xB < zD < yC，这三个数字字符串都包含相同的数字。

In order for that to be true, we must have x <= z <= y. Since y is the smallest digit > x, z cannot be between them, so either z = x or z = y. Say z = x. Then our inequality is xB < xD < yC, which means B < D where both B and D have the same digits. However, B is sorted descending, so there is no string with those digits larger than it. Thus we cannot have B < D. Following the same steps, we see that if z = y, we cannot have D < C.

为了这是真的,我们必须有x < = z < = y y。因为是最小的数字> x,z不能,所以z = x或z = y,z = x。那么我们的不平等是xB < xD < yC,这意味着B < D B和D有相同的数字。但是，B是按降序排列的，所以没有字符串比它大。因此，我们不能有B < D。按照相同的步骤，我们可以看到，如果z = y，我们就不能有D < C。

Therefore N' cannot exist, which means our algorithm correctly finds the next largest number.

因此N'不能存在，这意味着我们的算法正确地找到了下一个最大的数字。

#2

An almost-identical problem appeared as a Code Jam problem and has a solution here:

一个几乎相同的问题出现在代码阻塞问题上，并有一个解决方案:

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

http://code.google.com/codejam/contest/dashboard?c=186264 s =授权= 1

Here's a summary of the method using an example:

下面是这个方法的总结:

34722641

A. Split the sequence of digits in two, so that the right part is as long as possible while remaining in decreasing order:

A.将数字序列一分为二，使正确的部分尽可能长，同时保持递减顺序:

34722 641

(If the entire number is in decreasing order, there's no bigger number to be made without adding digits.)

(如果整个数字都是递减的，那么没有增加数字就没有更大的数字了。)

B.1. Select the last digit of the first sequence:

责任。选择第一个序列的最后一个数字:

3472(2) 641

B.2. Find the smallest digit in the second sequence that is larger than it:

B.2。在第二个序列中找到比它大的最小的数字:

3472(2) 6(4)1

B.3. Swap them:

B.3。交换:

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

C. Sort the second sequence into increasing order:

C.将第二个序列排序为递增顺序:

34724 126

D. Done!

d .完成了!

34724126

#3

Here's a compact (but partly brute force) solution in Python

这里是Python中一个紧凑(但部分是蛮力)的解决方案。

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

In C++ you could make the permutations like this: https://*.com/a/9243091/1149664 (It's the same algorithm as the one in itertools)

在c++中，您可以这样做:https://*.com/a/9243091/1149664(它与itertools中的算法相同)

Here's an implementation of the top answer described by Weeble and BlueRaja, (other answers). I doubt there's anything better.

下面是Weeble和BlueRaja(其他答案)所描述的最佳答案的实现。我怀疑还有什么更好的。

def findnext(ii):
    iis=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)))))

#4

At minimum, here are a couple of example brute force String based solutions, that you should have been able to come up with right off the top of your head:

至少，这里有一些基于暴力的基于字符串的解决方案，你应该能够从你的头顶上找到答案:

the list of digits in 38276 sorted is 23678

38276排序的数字列表为23678。

the list of digits in 38627 sorted is 23678

排在38627的数字列表是23678。

brute force increment, sort and compare

蛮力增量，排序和比较。

Along the brute force solutions would be convert to a String and brute force all the possible numbers using those digits.

在蛮力解决方案中，将会转换成一个字符串，并使用这些数字来强制所有可能的数字。

Create ints out of them all, put them in a list and sort it, get the next entry after the target entry.

创建所有的ints，把它们放在一个列表中，然后排序，在目标条目之后获得下一个条目。

If you spent 30 minutes on this and didn't at least come up with at least a brute force approach, I wouldn't hire you either.

如果你在这个问题上花了30分钟的时间，并且没有至少想出一个蛮力的方法，我也不会雇佣你。

In the business world, a solution that is inelegant, slow and clunky but gets the job done is always more valuable than no solution at all, matter of fact that pretty much describes all business software, inelegant, slow and clunky.

在商业世界中，一个不优雅、缓慢和笨拙的解决方案总是比没有解决方案更有价值，事实上，几乎所有的商业软件都是如此，不优雅、缓慢和笨拙。

#5

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

#6

Your idea

你的想法

I wanted to begin by finding the index of the first digit (from the right) that was less than the ones digit. Then I would rotate the last digits in the subset such that it was the next biggest number comprised of the same digits, but got stuck.

我想先找到小于个位数的第一个数字(从右边)的索引。然后我将最后一个数字在子集里旋转它是下一个最大的数字由相同的数字组成，但是被卡住了。

is pretty good, actually. You just have to consider not only the last digit but all digits of less significance than the currently considered. Since before that is reached, we have a monotonic sequence of digits, that is the rightmost digit smaller than its right neighbour. Regard

很好,真的。你不仅要考虑最后一个数字，而且要考虑所有小于当前考虑的数字。从那之前，我们有一个单调的数字序列，它比它的右邻右位数小。把

1234675
    ^

The next larger number having the same digits is

有相同数字的下一个更大的数是。

1234756

The found digit is exchanged for the last digit - the smallest of the considered digits - and the remaining digits are arranged in increasing order.

所发现的数字是交换的最后一个数字-最小的被认为的数字-和其余的数字排列在增加的顺序。

#7

I'm fairly sure your interviewer was trying to push you gently towards something like this:

我很确定你的面试官想把你轻轻推到这样的地方:

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

Not necessarily the most efficient or elegant solution but it solves the provided example in two cycles and swaps digits one at a time like he suggested.

不一定是最高效或最优雅的解决方案，但它解决了两个周期中提供的示例，并像他建议的那样，一次交换一个数字。

#8

That is very interesting question.

这是个很有趣的问题。

Here is my java version. Take me about 3 hours from figuring out the pattern to completely finish the code before I checked other contributors' comments. Glad to see my idea is quite same with others.

这是我的java版本。在我查看其他贡献者的注释之前，花3个小时的时间来找出完全完成代码的模式。很高兴看到我的想法和别人是一样的。

O(n) solution. Honestly, I will fail this interview if the time is only 15 minutes and require complete code finish on white board.

O(n)的解决方案。坦白地说，如果时间只有15分钟，并且要求在白板上完成完整的代码，我将会失败。

Here are some points of interesting for my solution:

下面是我的解决方案中一些有趣的地方:

• Avoid any sorting .
• 避免任何排序。
• Avoid string operation completely
• 完全避免字符串操作
• Achieve O(logN) space complexity
• 实现O(logN)空间的复杂性

I put detail comment in my code, and the Big O in each step.

我在代码中添加了细节注释，每一步都添加了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;

}

Here is result running in Intellj:

下面是智力的结果:

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

#9

Take a number and split it into digits. So if we have a 5 digit number, we have 5 digits: abcde

取一个数字，把它分成数字。如果我们有一个5位数，我们有5位数字:abcde。

Now swap d and e and compare with the original number, if it is larger, you have your answer.

现在交换d和e，和原来的数字相比，如果它更大，你就得到了答案。

If it isn't larger, swap e and c. Now compare and if it is smaller swap d and e again (notice recursion), take smallest.

如果它不是更大，交换e和c。现在比较，如果它是更小的交换d和e(注意递归)，取最小值。

Carry on through until you find a larger number. With recursion it should work out as about 9 lines of scheme, or 20 of c#.

继续前进，直到你找到一个更大的数字。使用递归时，它应该是大约9行方案，或20个c#。

#10

A javascript implementation of @BlueRaja's algorithm.

@BlueRaja算法的javascript实现。

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

#11

I've only tested this with two numbers. They worked. As IT Manager for 8 years until retiring last December, I cared about three things: 1) Accuracy: it's good if it works - always. 2) Speed: has to be acceptable to the user. 3) Clarity: I'm probably not as smart as you are, but I'm paying you. Make sure you explain what you're doing, in English.

我只测试了两个数字。他们工作。在去年12月退休之前的8年里，我一直关注着三件事:1)准确性:如果它能奏效，那就太好了——永远。2)速度:用户可接受。3)清楚:我可能不如你聪明，但我付钱给你。一定要用英语解释你在做什么。

Omar, best of luck going forward.

奥马尔，祝你好运。

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

#12

If you are programming in C++, you could use next_permutation:

如果你在c++编程，你可以使用next_per突变:

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

#13

I didn't know anything about the brute force algorithm when answering this question, so I approached it from another angle. I decided to search the entire range of possible solutions that this number could possibly be rearranged into, starting from the number_given+1 up to the max number available (999 for a 3 digit number, 9999 for 4 digits, etc.). I did this kind of like finding a palindrome with words, by sorting the numbers of each solution and comparing it to the sorted number given as the parameter. I then simply returned the first solution in the array of solutions, as this would be the next possible value.

当我回答这个问题时，我对这个蛮力算法一无所知，所以我从另一个角度来研究它。我决定搜索这个数字可能被重新排列的所有可能的解决方案，从number_given+1到可用的最大数字(999为3位数字，9999为4位数，等等)。我这样做就像用文字找到一个回文，通过对每个解的个数进行排序并将其与作为参数的排序数进行比较。然后，我简单地返回了解决方案数组中的第一个解决方案，因为这将是下一个可能的值。

Here is my code in Ruby:

下面是我在Ruby中的代码:

def PermutationStep(num)

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

结束

#14

A solution (in Java) could be the following (I am sure friends here can find a better):
Start swapping digits from the end of the string until you get a higher number.
I.e. first start moving up the lower digit.Then the next higher etc until you hit the next higher.
Then sort the rest. In your example you would get:

一个解决方案(在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));
}

#15

For a nice write-up of how to do this, see "Algorithm L" in Knuth's "The Art of Computer Programming: Generating all Permutations" (.ps.gz).

要想知道如何做到这一点，请参阅Knuth的“计算机编程艺术:生成所有排列”(.ps.gz)的“算法L”。

#16

Here is my code, it's a modified version of this example

这是我的代码，它是这个例子的修改版本。

Library:

库:

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

#17

Add 9 to the given n digit number. Then check if it is within the limit(the first (n+1) digit number). If it is then check if the digits in the new number are the same as the digits in the original number. Repeat adding 9 until both the conditions are true. Stop the algo when the number goes beyond the limit.

在给定的n位数上加9。然后检查它是否在限制内(第一个(n+1)位数字)。如果是，则检查新数字中的数字是否与原始数字中的数字相同。重复添加9，直到两个条件都为真。当数字超出限制时，停止algo。

I could not come up with a contradicting test case for this method.

我无法提出一个与此方法相矛盾的测试用例。

#18

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

#19

Just another solution using python:

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

Output:

输出:

23541

#20

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

    }

#21

Below is the code to generate all permutations of a number .. though one has to convert that integer to string using String.valueOf(integer) first.

下面是生成一个数字的所有排列的代码。尽管必须先将该整数转换为字符串。

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

#22

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

#23

here is my implementation of it in ruby:

下面是我在ruby中的实现:

def foo num  
  num = num.to_s.chars.map(&:to_i)
  return num.join.to_i if num.size < 2
  for left in (num.size-2).downto(0) do
    for right in (num.size-1).downto(left+1) do
      if num[right]>num[left]
        num[left],num[right] = num[right],num[left]        
        return (num[0..left] + num[left+1..num.size-1].sort).join.to_i
      end
    end
  end
  return num.join.to_i
end

p foo 38276 
#will print: 38627

you can read more here

你可以在这里读到更多。

#24

Yet another Java implementation, runnable out of the box and completed with tests. This solution is O(n) space and time using good old dynamic programming.

还有另一个Java实现，可以从框中运行，并通过测试完成。这个解决方案是O(n)空间和时间使用好的旧的动态规划。

If one wants to bruteforce, there are 2 kinds of bruteforce:

如果一个人想要bruteforce，有两种bruteforce:

1. Permute all the things, then pick min higher: O(n!)

   把所有的东西都打乱，然后再挑高一点:O(n!)

2. Similar to this implementation, but instead of DP, bruteforcing the step of populating the indexToIndexOfNextSmallerLeft map will run in O(n^2).

   类似于这种实现,而是DP,bruteforcing填充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);
    }

}

#25

We need to find the right most bit 0 followed by a 1 and flip this right most 0 bit to a 1.

我们需要找到最右边的0，然后是1，然后把这个最右边的0位加到1。

for example lets say our input is 487, which is 111100111 in binary.

例如，假设输入是487，它是二进制的111100111。

we flip the right most 0 that has 1 following it

我们翻转右边的0，它有1。

so we get 111101111

我们得到111101111

but now we have a extra 1 and one less 0, so we reduce the number of 1's on the right of the flip bit by 1 and increase the no of 0 bits by 1, yielding

但是现在我们有一个额外的1和一个更少的0，所以我们把1的右边的数减少1，然后把0位增加1，得到。

111101011 - binary 491

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

#26

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

#27

Here is the Java Implementation

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

Here is the Unit Tests

这是单元测试。

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

#28

I know this is very old question but still I didn't find easy code in c#. This might help guys who are attending interviews.

我知道这是一个很老的问题，但是我仍然没有找到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;
    }
}

#29

Very simple implementation using Javascript, next highest number with same digits

非常简单的实现，使用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);

Since there are lot of comments, so it's better you can copy it to your text editor. Thanks!

因为有很多的评论，所以你最好把它复制到你的文本编辑器中。谢谢!

#30

There are lots of good answers but I didn't find a decent Java implementation. Here is my two cents:

有很多好的答案，但是我没有找到一个像样的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;
}