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

关于如何做到这一点，请参阅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;
}

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

一个几乎相同的问题出现了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

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

我们需要找到最右边的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;
}