我只测试了两个数字。他们工作。 在去年12月退休之前，我做了8年的IT经理，我关心三件事: 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

Ruby的解决方案

def next_bigger(num)
  char_array = num.to_s.split('')
  return -1 if char_array.uniq.size == 1

  arr, target_idx, target_char = [], nil, nil
  # get first left-digit less than the right from right side
  (char_array.count - 1).times do |i|
    arr.unshift(char_array[-(i+1)])

    if char_array[-(i+2)] < char_array[-(i+1)]
      target_idx = char_array.count - (i + 2)
      target_char = char_array[-(i+2)]
      arr.unshift(char_array[-(i+2)])
      break
    end
  end
  return -1 unless target_idx

  # first smallest digit larger than target_char to the right
  ((target_char.to_i + 1)..9).to_a.each do |ch|
    if arr.index(ch.to_s)
      flip_char = arr.delete_at(arr.index(ch.to_s))
      # sort the digits to the right of flip_char
      arr.sort!
      # place flip_char to the left of target_char
      arr.unshift(flip_char)
      break
    end
  end

  (char_array[0...target_idx] + arr).join().to_i
end

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

我们需要找到最右边的0位，后面是1，然后将最右边的0位翻转为1。

例如，我们的输入是487，也就是二进制的111100111。

我们把后面有1的0往右翻转最多

所以我们得到 111101111

但是现在我们多了一个1，少了一个0，所以我们减少了右边1的个数 位增加1，并将0位的no增加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;
}

这是另一个Java实现，可以开箱即用，并通过测试完成。 这个解决方案是O(n)个空间和时间，使用老式的动态规划。

如果你想用蛮力，有两种蛮力:

排列所有的东西，然后选择最小值更高的:O(n!) 与此实现类似，但不是DP，而是强制填充的步骤 indexToIndexOfNextSmallerLeft映射将在O(n²)中运行。

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

}

这是个很有趣的问题。

这是我的java版本。在我检查其他贡献者的评论之前，从弄清楚模式到完全完成代码，我花了大约3个小时。很高兴看到我的想法和别人一样。

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

以下是我的解决方案的一些有趣点:

避免任何排序。 完全避免字符串操作 实现O(logN)空间复杂度

我在代码中添加了详细注释，并在每个步骤中添加了大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