你可以这样做O(n)（其中n位数）是这样的：
从右边开始，你会找到第一对数字，使得左边的数字小于右边的数字。让我们用“digit-x”来指代左边的数字。在 digit-x 的右侧找到大于 digit-x 的最小数，并将其放在 digit-x 的左侧。最后，按升序对剩余的数字进行排序——因为它们已经按降序排列，所以您需要做的就是将它们反转（除了 digit-x，它可以放在 中的正确位置O(n)）。
一个例子将使这一点更清楚：
123456784987654321
以数字开头
123456784 987654321
^从右数第一个左数小于右数的位置
数字“x”是 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。说z = x。那么我们的不等式是xB < xD < yC，这意味着B < D两者B和D具有相同的数字。但是，B 是按降序排序的，因此没有比它大的数字的字符串。因此我们不能拥有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
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
您拆分数字，这样您就知道没有更大的数字具有相同的左侧部分，您将左侧部分增加了尽可能少的数量，并使剩余的右侧部分尽可能小，因此您可以确定这个新数字是可以用相同的数字集合组成的最小的较大数字。
这是 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。
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
@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;
};
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++ 编程，您可以使用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 中）可能如下（我相信这里的朋友可以找到更好的）：
从字符串的末尾开始交换数字，直到你得到一个更高的数字。
即首先开始向上移动较低的数字。然后下一个更高的等，直到你达到下一个更高的位置。
然后对其余的进行排序。在您的示例中，您将获得：
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));
}
在回答这个问题时，我对蛮力算法一无所知，所以我从另一个角度接近它。我决定搜索这个数字可能被重新排列的所有可能的解决方案，从 number_given+1 到可用的最大数字（3 位数字为 999，4 位数字为 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
#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;
}
使用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
给给定的 n 位数字加 9。然后检查它是否在限制内（第一个（n + 1）位数字）。如果是，则检查新号码中的数字是否与原始号码中的数字相同。重复加 9，直到两个条件都为真。当数量超过限制时停止算法。
我无法为这种方法提出一个矛盾的测试用例。
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);
}
}
另一个 Java 实现，开箱即用，并通过测试完成。该解决方案是使用良好的旧动态规划的 O(n) 空间和时间。
如果要暴力破解，有两种暴力破解：
置换所有的东西，然后选择更高的最小值：O(n!)
与此实现类似，但不是 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);
}
}
下面是生成数字的所有排列的代码.. 尽管必须首先使用 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;
}
有关如何执行此操作的精彩文章，请参阅Knuth 的“计算机编程艺术：生成所有排列”(.ps.gz)中的“算法 L ”。
#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;
}
我只用两个数字对此进行了测试。他们工作了。作为 IT 经理 8 年直到去年 12 月退休，我关心三件事： 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
我们需要找到最右边的 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;
}
这是我在 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
这是我的代码，它是这个例子的修改版本
图书馆：
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);
}
这是我在 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));
}
我知道这是一个非常古老的问题，但我仍然没有在 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;
}
}
这是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));
}
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");
}
红宝石解决方案
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
在 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;
}
使用 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);
由于有很多评论，所以最好将其复制到文本编辑器中。谢谢！
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;
}
有很多好的答案，但我没有找到一个像样的 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;
}
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);
}
Answer in java with one more condition added
Next number should also be an Even number
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;
}
#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;
}
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();
}
}