我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
我刚刚搞砸了一次面试,而且我的面试问题几乎毫无进展。
给定一个数,找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
面试官还建议我试着一次换一个数字,但我搞不懂算法,只能盯着屏幕看20-30分钟。不用说,我想我还得继续找工作。
当前回答
下面是Python中的一个紧凑(但部分是蛮力)解决方案
def findnext(ii): return min(v for v in (int("".join(x)) for x in
itertools.permutations(str(ii))) if v>ii)
在c++中,你可以这样排列:https://stackoverflow.com/a/9243091/1149664(它与itertools中的算法相同)
以下是Weeble和BlueRaja描述的顶部答案的实现(其他答案)。我怀疑还有什么更好的办法。
def findnext(ii):
iis=list(map(int,str(ii)))
for i in reversed(range(len(iis))):
if i == 0: return ii
if iis[i] > iis[i-1] :
break
left,right=iis[:i],iis[i:]
for k in reversed(range(len(right))):
if right[k]>left[-1]:
right[k],left[-1]=left[-1],right[k]
break
return int("".join(map(str,(left+sorted(right)))))
其他回答
public static void findNext(long number){
/* convert long to string builder */
StringBuilder s = new StringBuilder();
s.append(number);
int N = s.length();
int index=-1,pivot=-1;
/* from tens position find the number (called pivot) less than the number in right */
for(int i=N-2;i>=0;i--){
int a = s.charAt(i)-'0';
int b = s.charAt(i+1)-'0';
if(a<b){
pivot = a;
index =i;
break;
}
}
/* if no such pivot then no solution */
if(pivot==-1) System.out.println(" No such number ")
else{
/* find the minimum highest number to the right higher than the pivot */
int nextHighest=Integer.MAX_VALUE, swapIndex=-1;
for(int i=index+1;i<N;i++){
int a = s.charAt(i)-'0';
if(a>pivot && a<nextHighest){
nextHighest = a;
swapIndex=i;
}
}
/* swap the pivot and next highest number */
s.replace(index,index+1,""+nextHighest);
s.replace(swapIndex,swapIndex+1,""+pivot);
/* sort everything to right of pivot and replace the sorted answer to right of pivot */
char [] sort = s.substring(index+1).toCharArray();
Arrays.sort(sort);
s.replace(index+1,N,String.copyValueOf(sort));
System.out.println("next highest number is "+s);
}
}
你的想法
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字,这样它是由相同的数字组成的下一个最大的数字,但卡住了。
其实还不错。您不仅要考虑最后一位数字,还要考虑所有比当前考虑的不那么重要的数字。在此之前,我们有一个单调的数字序列,即最右边的数字比它右边的邻居小。把
1234675
^
下一个有相同数字的大数是
1234756
将找到的数字交换为最后一位数字(考虑的数字中最小的数字),其余数字按递增顺序排列。
private static int GetNextHigherNumber(int num)
{
//given 38276 return 38627
string numberstring = num.ToString();
char[] sNum = numberstring.ToCharArray();
for (int i = sNum.Length - 1; i > 0; i--)
{
for (int j = i - 1; j > 0; j--)
{
if (sNum[i] > sNum[j])
{
for (int x = i; x > j; x--)
{
char chr = sNum[x];
sNum[x] = sNum[x - 1];
sNum[x - 1] = chr;
}
i = 0;
break;
}
}
}
numberstring = string.Empty;
for(int x= 0 ; x<sNum.Length;x++)
{
numberstring += sNum[x].ToString();
}
return Convert.ToInt32(numberstring);
}
我知道这是一个非常老的问题,但我仍然没有在c#中找到简单的代码。这可能会对参加面试的男士有所帮助。
class Program
{
static void Main(string[] args)
{
int inputNumber = 629;
int i, currentIndexOfNewArray = 0;
int[] arrayOfInput = GetIntArray(inputNumber);
var numList = arrayOfInput.ToList();
int[] newArray = new int[arrayOfInput.Length];
do
{
int temp = 0;
int digitFoundAt = 0;
for (i = numList.Count; i > 0; i--)
{
if (numList[i - 1] > temp)
{
temp = numList[i - 1];
digitFoundAt = i - 1;
}
}
newArray[currentIndexOfNewArray] = temp;
currentIndexOfNewArray++;
numList.RemoveAt(digitFoundAt);
} while (arrayOfInput.Length > currentIndexOfNewArray);
Console.WriteLine(GetWholeNumber(newArray));
Console.ReadKey();
}
public static int[] GetIntArray(int num)
{
IList<int> listOfInts = new List<int>();
while (num > 0)
{
listOfInts.Add(num % 10);
num = num / 10;
}
listOfInts.Reverse();
return listOfInts.ToArray();
}
public static double GetWholeNumber(int[] arrayNumber)
{
double result = 0;
double multiplier = 0;
var length = arrayNumber.Count() - 1;
for(int i = 0; i < arrayNumber.Count(); i++)
{
multiplier = Math.Pow(10.0, Convert.ToDouble(length));
result += (arrayNumber[i] * multiplier);
length = length - 1;
}
return result;
}
}
至少,这里有几个基于字符串的暴力解决方案的例子,你应该能够马上想到:
38276中的数字排序为23678
38627排序的数字列表是23678
蛮力增量,排序和比较
沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。
从它们中创建int,把它们放在一个列表中并排序, 获取目标条目之后的下一个条目。
如果你花了30分钟在这个问题上,却没有想出一个蛮力的方法,我也不会雇用你。
在商业世界中,一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值,事实上,这几乎描述了所有不优雅、缓慢和笨拙的商业软件。