给定一个数字，找出下一个与原始数字具有完全相同的数字集的更高的数字

至少，这里有几个基于字符串的暴力解决方案的例子，你应该能够马上想到:

38276中排序的数字列表是23678

38627中排序的数字列表是23678

蛮力增量，排序和比较

沿着暴力解决方案将转换为一个字符串 并使用这些数字强行计算所有可能的数字

从它们中创建int，把它们放在一个列表中并排序，

如果你花了30分钟在这个问题上，却没有想出一个蛮力的方法，我也不会雇用你。

在商业世界中，一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值，事实上，这几乎描述了所有商业软件，不优雅、缓慢和笨拙。

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

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

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

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

一直算下去，直到找到一个更大的数字。通过递归，它应该相当于9行方案，或20行c#。

你的想法

我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。

其实还不错。您不仅要考虑最后一位数字，还要考虑所有比当前考虑的不那么重要的数字。在此之前，我们有一个单调的数字序列，即最右边的数字比它右边的邻居小。把

1234675
^

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

1234756

将找到的数字交换为最后一位数字(考虑的数字中最小的数字)，其余数字按递增顺序排列。

你可以在O(n)中这样做(其中n是位数):

从右边开始，找到左位数小于右位数的第一对数字。让我们用“digit-x”来表示左边的数字。在数字-x的右边找到比数字-x大的最小的数，并把它放在数字-x的左边。最后，对剩余的数字进行升序排序——因为它们已经是下行的顺序，你所需要做的就是将它们倒序(保存为digit-x，它可以放在O(n)中的正确位置)。

举个例子可以更清楚地说明这一点:

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'

正确性证明:

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

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

为了使这个为真，我们必须有x <= z <= y。因为y是最小的数字> x，所以z不能在它们之间，所以z = x或z = y。z = x说。那么我们的不等式是xB < xD < yC，这意味着B < D，其中B和y0有相同的数字。然而，B是降序排序的，所以y4没有比它大的数字的字符串。因此我们不能有B < D。按照同样的步骤，我们可以看到如果z = y，就不能有y3。

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

下面是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)))))

一个几乎相同的问题出现了Code Jam问题，这里有一个解决方案:

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

下面用一个例子总结一下这个方法:

34722641

A.将数字序列分成两部分，使右边的部分尽可能长，同时保持递减顺序:

34722 641

(如果整个数字是递减的，则没有更大的数字可以在不添加数字的情况下生成。)

在这一点上，你知道没有从左边开始的更大的数了，因为右边的剩余数字已经尽可能大了。

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

3472(2) 641

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

3472(2) 6(4)1

你所做的是寻找最小的可能增加的左边部分。

B.3。交换:

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

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

34724 126

d .完成了!

34724126

你把这个数字分开，这样你就知道没有更大的数字具有相同的左边部分，你把左边部分增加了尽可能小的量，你让剩下的右边部分尽可能小，所以你可以确保这个新数字是用相同的数字集合可以得到的最小的更大的数字。

我很确定你的面试官是想委婉地让你说出这样的话:

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

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

奥马尔，祝你好运。

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

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

如果你用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;
}

这是个很有趣的问题。

这是我的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

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

库:

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

给n位数字加9。然后检查它是否在限制范围内(第一个(n+1)位数)。如果是，则检查新号码中的数字是否与原号码中的数字相同。 重复加9，直到两个条件都为真。

对于这种方法，我想不出一个与之相矛盾的测试用例。

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

只是使用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);
}


}

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

下面是我的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

回答在java与一个更多的条件添加

• 下一个数字也应该是偶数

   public static int nextDigit(int number) {
  String num = String.valueOf(number);
  int stop = 0;
  char[] orig_chars = null;
  char[] part1 = null;
  char[] part2 = null;
  orig_chars = num.toCharArray();
  
  
  System.out.println("vivek c r");
  for (int i = orig_chars.length - 1; i > 0; i--) {
  String previous = orig_chars[i - 1] + "";
  String next = orig_chars[i] + "";
  if (Integer.parseInt(previous) < Integer.parseInt(next))
  
  
  {
  if (Integer.parseInt(previous) % 2 == 0) {
  
  
  String partString1 = "";
  String partString2 = "";
  for (int j = 0; j <= i - 1; j++) {
  partString1 = partString1.concat(orig_chars[j] + "");
  }
  part1 = partString1.toCharArray();
  for (int k = i; k < orig_chars.length; k++) {
  partString2 = partString2.concat(orig_chars[k] + "");
  }
  part2 = partString2.toCharArray();
  Arrays.sort(part2);
  for (int l = 0; l < part2.length; l++) {
  char temp = '0';
  if (part2[l] > part1[i - 1]) {
  temp = part1[i - 1];
  part1[i - 1] = part2[l];
  part2[l] = temp;
  break;
  }
  }
  for (int m = 0; m < part2.length; m++) {
  char replace = '0';
  if (part2[m] % 2 == 0) {
  replace = part2[m];
  for (int n = m; n < part2.length - 1; n++) {
  part2[n] = part2[n + 1];
  }
  part2[part2.length - 1] = replace;
  break;
  }
  }
  
  
  System.out.print(part1);
  System.out.println(part2);
  System.exit(0);
  }
  }
  }
  System.out.println("NONE");
  
  
  return 0;
  }
  

 private static int GetNextHigherNumber(int num)
{
//given 38276 return 38627


string numberstring = num.ToString();


char[] sNum = numberstring.ToCharArray();


for (int i = sNum.Length - 1; i > 0; i--)
{
for (int j = i - 1; j > 0; j--)
{
if (sNum[i] > sNum[j])
{
for (int x = i; x > j; x--)
{
char chr = sNum[x];
sNum[x] = sNum[x - 1];
sNum[x - 1] = chr;
}


i = 0;
break;
}
}
}


numberstring = string.Empty;
for(int x= 0 ; x<sNum.Length;x++)
{
numberstring += sNum[x].ToString();
}


return Convert.ToInt32(numberstring);
}

下面是生成一个数字的所有排列的代码..不过必须先使用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;
}

这是我在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

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

1. 排列所有的东西，然后选择最小值更高的:O(n!)

2. 类似于这个实现，但不是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);
}


}

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

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

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

所以我们得到 111101111 < / p >

但是现在我们多了一个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;
}

#include <iostream>
using namespace std;


int main ()
{
int num=15432;
int quot,rem;
int numarr[5];
int length=0;
while(num!=0)
{
rem=num%10;
num = num/10;
numarr[length]=rem;
length++;
}


for(int j=0;j<length;j++)
{
for(int i=0;i<length;i++)
{
if(numarr[i]<numarr[i+1])
{
int tmp=numarr[i];
numarr[i]=numarr[i+1];
numarr[i+1]=tmp;
}
}
}


for(int j=0;j<length;j++)
{
cout<<numarr[j];
}
return 0;
}

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

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

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

import java.util.Scanner;
public class Big {


public static void main(String[] args) {




Scanner sc = new Scanner(System.in);
System.out.print("Enter the number ");
String str = sc.next();
int t=0;


char[] chars  = str.toCharArray();






for(int i=str.length()-1,j=str.length()-2;j>=0;j--)
{




if((int)chars[i]>(int)chars[j])
{
t = (int)chars[i];
chars[i] = chars[j];
chars[j]=(char)t;


for(int k=j+1;k<str.length()-1;k++)
{
for(int l=k+1;l<str.length();l++)
{
if(chars[k]>chars[l])
{
int m = (int)chars[k];
chars[k] = chars[l];
chars[l]=(char)m;
}
}
}


break;
}












}
System.out.print("The next Big number is: ");


for(int i=0;i<str.length();i++){
System.out.print(chars[i]);
}
sc.close();
}




}

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

在Java中，这是一个比这更紧凑的算法答案

   public static int permutate2(int number){
String[] numArray = String.valueOf(number).split("");


for(int i = numArray.length - 1; i > 0; i--){
int current = Integer.valueOf(numArray[i]);
int previous = Integer.valueOf(numArray[i - 1]);


if(previous < current){
String[] rest = String.valueOf(number).substring(i, numArray.length).split("");
Arrays.sort(rest);


String picker = rest[0];
int pickerIndex = 0;
for(int n = 0; n < rest.length ; n++){
if(Integer.valueOf(rest[n]) > previous){
picker = rest[n];
pickerIndex = n;
break;
}
}
numArray[i - 1] = picker;
rest[pickerIndex] = String.valueOf(previous);
Arrays.sort(rest);


String newNumber = "";
for(int z = 0; z <= i - 1; z++){
newNumber += numArray[z];
}
for(String z : rest){
newNumber += z;
}


return Integer.valueOf(newNumber);
}
}


return number;
}

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

这里有一个我在c#中没有想到的聪明的解决方案

 using System;
using System.Linq;


public static long NextBiggerNumber(long n)
{
String str = GetNumbers(n);
for (long i = n+1; i <= long.Parse(str); i++)
{
if(GetNumbers(n)==GetNumbers(i))
{
return i;
}
}
return -1;
}
public static string GetNumbers(long number)
{
return string.Join("", number.ToString().ToCharArray().OrderByDescending(x => x));
}

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

PHP实现

时间复杂度O(n)

$n = "9875";
$n_size = strlen($n);
for($i = $n_size-1; $i > 0; $i-- ) {
if($n[$i] > $n[$i-1]){
$temp = $n[$i];
$n[$i] = $n[$i-1];
$n[$i-1] = $temp;
break;
}
    

}


if($i == 0){
echo "Next Greater value no possible";
}else{
echo $n;
}