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

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

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

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


当前回答

有很多不错的答案,但我没有找到一个像样的Java实现。以下是我的观点:

public void findNext(int[] nums) {
    int i = nums.length - 1;
    // nums[i - 1] will be the first non increasing number
    while (i > 0 && nums[i] <= nums[i - 1]) {
        i--;
    }
    if (i == 0) {
        System.out.println("it has been the greatest already");
    } else {
        // Find the smallest digit in the second sequence that is larger than it:
        int j = nums.length - 1;
        while (j >= 0 && nums[j] < nums[i - 1]) {
            j--;
        }
        swap(nums, i - 1, j);
        Arrays.sort(nums, i, nums.length);
        System.out.println(Arrays.toString(nums));
    }
}

public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

其他回答

import java.util.Scanner;
public class Big {

    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number ");
        String str = sc.next();
        int t=0;

        char[] chars  = str.toCharArray();



        for(int i=str.length()-1,j=str.length()-2;j>=0;j--)
        {


                if((int)chars[i]>(int)chars[j])
                {
                    t = (int)chars[i];
                    chars[i] = chars[j];
                    chars[j]=(char)t;

                    for(int k=j+1;k<str.length()-1;k++)
                    {
                        for(int l=k+1;l<str.length();l++)
                        {
                            if(chars[k]>chars[l])
                            {
                                int m = (int)chars[k];
                                chars[k] = chars[l];
                                chars[l]=(char)m;
                            }
                        }
                    }

                    break;
                }






        }
        System.out.print("The next Big number is: ");

        for(int i=0;i<str.length();i++){
            System.out.print(chars[i]);
        }
        sc.close();
    }


}

这是我在Ruby中的实现:

def foo num  
  num = num.to_s.chars.map(&:to_i)
  return num.join.to_i if num.size < 2
  for left in (num.size-2).downto(0) do
    for right in (num.size-1).downto(left+1) do
      if num[right]>num[left]
        num[left],num[right] = num[right],num[left]        
        return (num[0..left] + num[left+1..num.size-1].sort).join.to_i
      end
    end
  end
  return num.join.to_i
end

p foo 38276 
#will print: 38627

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

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);

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

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

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

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

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

关于如何做到这一点,请参阅Knuth的“计算机编程艺术:生成所有排列”(.ps.gz)中的“算法L”。