算法--找出与目标数字相同的字符组成的整数中比该数字大的数集中的最小数字

题目:

给出1个正整数，找到用与这个数字相同的digit组成的整数中比这个数字大的数集中的最小数字。比如：12352874 的结果是 12354278

分析:

这道题目的考虑目标是数组的查找与排序.

当然, 前提是你得明白这道题目的思路是什么样子的. 把正整数转化为char数组a, 长度为n, 末尾字符是a[n-1], 然后对该数组逆序查找, 会发现, 第一个a[n-1]比小的字符是a[i], 然后字符a[i]跟a[n-1]交换, 最后对数组中i+1到n-1的部分进行升级排序, 你会发现, 正是最后的结果正是比目标整数大的数集中最小的数字.

示例中数字的分析过程为:

[1, 2, 3, 5, 2, 8, 7, 4]

^(2 < 4, 交换)

[1, 2, 3, 5, 4, 8, 7, 2]

^, 然后对后三位字符升级排序, 结果为:

[1, 2, 3, 5, 4, 2, 7, 8]

同样, 再对上述结果继续上述操作, 其后续结果依次是:

[1, 2, 3, 5, 4, 2, 8, 7]

[1, 2, 3, 5, 4, 7, 2, 8]

[1, 2, 3, 5, 4, 7, 8, 2]

[2, 1, 2, 3, 4, 5, 7, 8]

......

由此, 上述思路的Java代码实现为:

    public int findCeil(int src) {
        char[] chars = String.valueOf(src).toCharArray();
        int index = -1;
        int lastIndex = chars.length - 1;
        char lastChar = chars[lastIndex];
        for (int i = chars.length - 2; i > -1; i--) {
            if (chars[i] < lastChar) {
                index = i;
                break;
            }
        }
        if (index > -1) {
            char ch = chars[index];
            chars[index] = lastChar;
            chars[lastIndex] = ch;
            quickSort(chars, index + 1, lastIndex);
        }
        return Integer.parseInt(String.valueOf(chars));
    }

然后, 其中为char数组进行快速排序的算法如下:

    public void quickSort(char[] chars, int start, int end) {
        if (chars != null && start > -1 && end < chars.length && start < end) {
            int i = start, j = end;
            char value = chars[start];
            while (i < j) {
                while (j > start && chars[j] >= value) {
                    j--;
                }
                if (i < j) {
                    chars[i] = chars[j];
                    i++;
                }
                while (i < end && chars[i] < value) {
                    i++;
                }
                if (i < j) {
                    chars[j] = chars[i];
                    j--;
                }
                chars[i] = value;
                quickSort(chars, start, i);
                quickSort(chars, i + 1, end);
            }
        }
    }

Update:

后来又想了一下, 上面的findCeil(int)方法并不完美. 如果给定1570, 目标数应该为1705, 但是findCeil(int)并不能找出来.

思路应该修改下: 当最后一个元素, 逆向遍历并不存在比它小的元素时, 应该再次从倒数第二个元素, 开始逆向遍历查找比它小的元素, 如果还找不到, 则从倒数第三个元素开始, 依此类推.

所以, 更新后的findCei(int)方法为:

 1 public int findCeil(int src) {
 2     char[] chars = String.valueOf(src).toCharArray();
 3     for (int i = chars.length - 1; i> -1; i--) {
 4     　　int index = -1;
 5     　　int lastIndex = i;
 6     　　char lastChar = chars[lastIndex];
 7         　for (int j = i - 1; j > -1; j--) {
 8             　if (chars[i] < lastChar) {
 9                 　index = i;
10                 　break;
11             　}
12         　}
13         　if (index > -1) {
14             　char ch = chars[index];
15             　chars[index] = lastChar;
16             　chars[lastIndex] = ch;
17             　quickSort(chars, index + 1, chars.length - 1);
18             　return Integer.parseInt(String.valueOf(chars));
19         　} else {
20             　continue;
21         　}
22     }
23     return src;
24 }

然后, 这题题目就完美的解决啦!