13 March 2015

陈利人面试题之: 给定一个数X,他的兄弟数Y定义为:是由X中的数字组合而成,并且Y是大于X的数中最小的。例如,38276的兄弟数字为38627。给定X,求Y。

原题及作者分析链接: http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000184&itemidx=1&sign=f080024b52b8bf130bd9c1c7860e4306

个人分析: 个人认为,求得Y其实有两种情况: 1. X里面的最后一位数比倒数第二位数要大: 这个时候,直接交换那两位就可以得到Y了。比如:1234567,它的兄弟数字就是1234576.(由原数字组成,并且是比原数字大的数字里面的最小的一个。) - X里面的最后一位数比倒数第二位要小: 这个时候,就可以参照链接里的分析:

假设X的形式如下:x1x2x3…xky1y2y3y4,并且其中y1>y2>y3>y4,xk 3 4 7 2 2 6 4 1
首先找到,从右边开始的递增的、尽可能长的数位,这里是641。
3 4 7 2 2 (6 4 1)
则,选取前一位数字2,进行交换。641中,大于2的最小的值是4,则作如下交换:
3 4 7 2 4 (6 2 1)
为了得到最小值,对621,从小到大进行排序,得到
3 4 7 2 4 1 2 6
则,Y为34724126.


下面是我自己的Java实现

执行结果如下:
The original numbers are: [897654, 979984653, 1234567, 3456123]
Their brother numbers are: [945678, 979985346, 1234576, 3456132]

package auguest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BrotherNumber {
    public static void main(String[] args) {
        List<String> orgNums = Arrays.asList("897654", "979984653", "1234567", "3456123");
        List<String> newNums = new ArrayList<String>();

        for (String orgNum : orgNums) {

            newNums.add(getBrotherNumber(orgNum));
        }

        System.out.println("The original numbers are: " + orgNums);
        System.out.println("Their brother numbers are: " + newNums);

    }

    public static String getBrotherNumber(String orgNum) {
        //定义一个新的字符串
        String newString = orgNum;
        int length = orgNum.length();

        char[] orgArray = orgNum.toCharArray();

        //比较最后两位,如果倒数第二位比最后一位大,则需要继续处理;如果小,则可以直接交换得到兄弟数列。
        if (compareEnd(orgArray[length-2], orgArray[length-1])) {

            char[] newArray = orgNum.toCharArray();

            //从倒数第二位往回找,直到找到之前的一位比当前位小的情况
            //比如:34568765,从6开始往左找,找到“8“这一位的位置
            int i = length - 2;
            while (i>0 & compareEnd(orgArray[i-1], orgArray[i])) {
                i --;
            }

            for (int j=length-1; j>i-1; j--) {
                if (compareEnd(orgArray[j], orgArray[i-1])) {
                    newArray = exchangeNumbers(orgArray, i-1, j);
                    break;
                }
            }

            String newFrontStr = new String(newArray, 0, i);

            char[] tmpArray = new String(newArray, i, length-i).toCharArray();
            Arrays.sort(tmpArray);

            newString = newFrontStr + new String(tmpArray);

        } else {
            newString = new String(exchangeNumbers(orgArray, length-2, length-1));
        }

        return newString;
    }


    public static boolean compareEnd(char last2, char last1) {
        return last2 > last1 ? true : false;
    }

    public static char[] exchangeNumbers(char[] orgCharArray, int pos1, int pos2) {
        char tmpChar = orgCharArray[pos2];
        orgCharArray[pos2] = orgCharArray[pos1];
        orgCharArray[pos1] = tmpChar;
        return orgCharArray;
    }

}

</div>