1. 题目

给定任意一个自然数，获取它重新排列后，下一个比它大的自然数，要求时间复杂度O(n)。例如： 给定1233,它的下一个是1323； 给定1323,它的下一个是1332； 给定9876,它的下一个不存在； 请设计一个函数，完成此功能。(语言不限)

2.思路

分析给出的三个例子,可以得到以下的步骤:

  1. 调换位置开始的地方，后一个数比前一个数大。例如 1233 ——> 1323 的 23 位置。
  2. 如果数据是从大到小的排列，那么得到的数其实是它自己。
  3. 调换位置开始以后的位置，需要将之后的数按照从小到大的排列。

3.代码实现

主要分为3步：

  1. 将数字转为数组。
  2. 对数组按照 思路 中的分析，进行处理。
  3. 将数组还原为数字。
/**
 * @brief 将nValue转为数组
 * 
 * @param  nValue 待转换的整数
 *         nArray 用来保存结果的数组
 *         nArrayLen nArray的最大长度
 * 
 * @return > 0 转换后的元素的个数
 *           0 数组长度不够，转换失败
 */
int IntToArray(const int nValue,int nArray[],const int nArrayLen)
{
    int nStep = 1;
    int nCount = 0;
    int nOldValue = nValue;
    while( nOldValue >= nStep && 
           nCount  < nArrayLen)
    {
        nArray[nCount]=(nOldValue/nStep)%10;
        nCount++;
        nStep *= 10;
    }
    if(nCount  < nArrayLen)
    {
        return nCount;
    }
    else
    {
        return -1;
    }
}


/**
 * @brief 将数组的内容转为整数，例如数组为{1,2,3,4}，转为整数为1234
 * 
 * @param nArray 待转换的数组
 *        nArrayLen 待转换的数组的长度
 * 
 * @return 转换后的结果
 */
int ArrayToInt(const int nArray[],const int nArrayLen)
{
    int nNewValue = 0;
    int nNewStep = 1;
    for(int index = 0 ; index <  nArrayLen ; index++)
    {
        nNewValue += nArray[index]*nNewStep;
        nNewStep*=10;
    }
    return nNewValue;
}

/**
 * @brief 排序用的比较函数
 * 
 */
bool CompareLess(const int nLeft,const int nRight)
{
    return nLeft > nRight;
}

/**
 * @brief 给定任意一个自然数，获取它重新排列后，下一个比它大的自然数，要求时间复杂度O(n)
 * 
 * @param oldValue 给定的自然数
 * 
 * @return 下一个数
 */
int GetNextValue(const int oldValue)
{
    int nArray[64]={0};
    int nStep = 10;
    int nCount = 0;
    int nOldValue = oldValue;
    nCount = IntToArray(oldValue,nArray,64);
    int nIndex = 0;

    while(nIndex  < nCount-1)
    {
        if(nArray[nIndex]  = nArray[nIndex+1])
        {
            nIndex++;
        }
        else
        {
            break;
        }
    }
    if(nIndex <  nCount-1)
    {
        std::sort(&nArray[0],&nArray[nIndex+1],CompareLess);
        int nTemp = nArray[nIndex];
        nArray[nIndex]=nArray[nIndex+1];
        nArray[nIndex+1]=nTemp;
    }

    return ArrayToInt(nArray,nCount);
}