输出下一个大自然数

柔情只为你懂 2022-01-28 11:49 191阅读 0赞

# [输出下一个大自然数][Link 1] #

给定任意一个自然数，获取它重新排列后，下一个比它大的自然数，要求时间复杂度O(n)。例如：

给定1233,它的下一个是1323；

给定1323,它的下一个是1332；

给定9876,它的下一个不存在；

请设计一个函数，完成此功能。(语言不限)

我的思路其实是遍历第一次 获取到数值值递增的波动点

然后 利用波动点位置 与后面的进行比较

最后达到一个递增的数列  关于实现采用了一些Java 包装类的api 大家可以参考参考

public class Test13 {
        public static Integer nextSortResult(Integer num) {
            String string = num.toString();
            char[] numChar = string.toCharArray();
            if (numChar[0]=='9') {
                return num; // 第一个是9的永远没有好戏可以上演了
            }
            int maxIndex = -1;
            int record = 0;
            for (int i = 0; i + 1 < numChar.length; i++) { // 遍历一遍 找到转折点记录下来 后面找到最大值
                if (numChar[i] > numChar[i + 1]) {
                    record = i + 1;
                }
            }
            for (int i = record + 1; i < numChar.length; i++) {
                if (numChar[i] > numChar[record]) {
                    maxIndex = i;
                }
            }
    
            swap(numChar, record, maxIndex);
            String stringNum = new String(numChar);
            int resultNum = Integer.valueOf(stringNum);
            return resultNum;
        }
    
        public static void swap(char[] arr, int k, int n) {
            char temp = arr[k];
            arr[k] = arr[n];
            arr[n] = temp;
    
        }
    
        public static void main(String[] args) {
            Integer num = 134238;
            Integer nextSortResult = nextSortResult(num);
            System.out.println(nextSortResult);
        }
    
    }

[Link 1]: https://www.cnblogs.com/toov5/p/10416204.html