我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。

给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627

我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。

面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。


当前回答

这里是Java实现

public static int nextHigherNumber(int number) {
    Integer[] array = convertToArray(number);
    int pivotIndex = pivotMaxIndex(array);
    int digitInFirstSequence = pivotIndex -1;
    int lowerDigitIndexInSecondSequence = lowerDigitIndex(array[digitInFirstSequence], array, pivotIndex);
    swap(array, digitInFirstSequence, lowerDigitIndexInSecondSequence);
    doRercursiveQuickSort(array, pivotIndex, array.length - 1);
    return arrayToInteger(array);
}

public static Integer[] convertToArray(int number) {
    int i = 0;
    int length = (int) Math.log10(number);
    int divisor = (int) Math.pow(10, length);
    Integer temp[] = new Integer[length + 1];

    while (number != 0) {
        temp[i] = number / divisor;
        if (i < length) {
            ++i;
        }
        number = number % divisor;
        if (i != 0) {
            divisor = divisor / 10;
        }
    }
    return temp;
}

private static int pivotMaxIndex(Integer[] array) {
    int index = array.length - 1;
    while(index > 0) {
        if (array[index-1] < array[index]) {
            break;
        }
        index--;
    }       
    return index;
}

private static int lowerDigitIndex(int number, Integer[] array, int fromIndex) {
    int lowerMaxIndex = fromIndex;
    int lowerMax = array[lowerMaxIndex];
    while (fromIndex < array.length - 1) {
        if (array[fromIndex]> number && lowerMax > array[fromIndex]) {
            lowerMaxIndex = fromIndex; 
        }
        fromIndex ++;
    }
    return lowerMaxIndex;
}

public static int arrayToInteger(Integer[] array) {
    int number = 0;
    for (int i = 0; i < array.length; i++) {
        number+=array[i] * Math.pow(10, array.length-1-i);
    }
    return number;
}

这里是单元测试

@Test
public void nextHigherNumberTest() {
    assertThat(ArrayUtils.nextHigherNumber(34722641), is(34724126));
    assertThat(ArrayUtils.nextHigherNumber(123), is(132));
}

其他回答

取一个数,把它分成几位数。如果我们有一个5位数,我们就有5位数:abcde

现在交换d和e,并与原来的数字进行比较,如果它更大,你就得到了答案。

如果它不是很大,交换e和c。现在比较,如果它更小,再次交换d和e(注意递归),取最小的。

一直算下去,直到找到一个更大的数字。通过递归,它应该相当于9行方案,或20行c#。

给定n位数字加9。然后检查它是否在限制范围内(第一个(n+1)位数)。如果是,则检查新号码中的数字是否与原号码中的数字相同。 重复加9,直到两个条件都为真。 当数字超过限制时停止算法。

对于这种方法,我想不出一个与之相矛盾的测试用例。

在Java中,这个算法比这个算法更简洁

   public static int permutate2(int number){
        String[] numArray = String.valueOf(number).split("");

        for(int i = numArray.length - 1; i > 0; i--){
            int current = Integer.valueOf(numArray[i]);
            int previous = Integer.valueOf(numArray[i - 1]);

            if(previous < current){
                String[] rest = String.valueOf(number).substring(i, numArray.length).split("");
                Arrays.sort(rest);

                String picker = rest[0];
                int pickerIndex = 0;
                for(int n = 0; n < rest.length ; n++){
                    if(Integer.valueOf(rest[n]) > previous){
                        picker = rest[n];
                        pickerIndex = n;
                        break;
                    }
                }
                numArray[i - 1] = picker;
                rest[pickerIndex] = String.valueOf(previous);
                Arrays.sort(rest);

                String newNumber = "";
                for(int z = 0; z <= i - 1; z++){
                    newNumber += numArray[z];
                }
                for(String z : rest){
                    newNumber += z;
                }

                return Integer.valueOf(newNumber);
            }
        }

        return number;
   }

我很确定你的面试官是想委婉地让你说出这样的话:

local number = 564321;

function split(str)
    local t = {};
    for i = 1, string.len(str) do
        table.insert(t, str.sub(str,i,i));
    end
    return t;
end

local res = number;
local i = 1;
while number >= res do
    local t = split(tostring(res));
    if i == 1 then
        i = #t;
    end
    t[i], t[i-1] = t[i-1], t[i];
    i = i - 1;
    res = tonumber(table.concat(t));
end

print(res);

不一定是最有效或最优雅的解决方案,但它在两个循环中解决了所提供的示例,并像他建议的那样一次交换一个数字。

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