我刚刚搞砸了一次面试，而且我的面试问题几乎毫无进展。
给定一个数，找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。
面试官还建议我试着一次换一个数字，但我搞不懂算法，只能盯着屏幕看20-30分钟。不用说，我想我还得继续找工作。
当前回答
我知道这是一个非常老的问题，但我仍然没有在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;
}
}
其他回答
PHP实现
时间复杂度O(n)
$n = "9875";
$n_size = strlen($n);
for($i = $n_size-1; $i > 0; $i-- ) {
if($n[$i] > $n[$i-1]){
$temp = $n[$i];
$n[$i] = $n[$i-1];
$n[$i-1] = $temp;
break;
}
}
if($i == 0){
echo "Next Greater value no possible";
}else{
echo $n;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,k,min,len,diff,z,u=0,f=0,flag=0;
char temp[100],a[100]`enter code here`,n;
min=9999;
//cout<<"Enter the number\n";
cin>>a;
len=strlen(a);
for(i=0;i<len;i++)
{
if(a[i]<a[i+1]){flag=1;break;}
}
if(flag==0){cout<<a<<endl;}
else
{
for(i=len-1;i>=0;i--)if(((int)a[i-1])<((int)a[i]))break;
for(k=0;k<i-1;k++)cout<<a[k];
for(j=i;j<len;j++)
{
if(((int)a[j]-48)-((int)a[i-1]-48)>0)
{
diff=((int)a[j]-48)-((int)a[i-1]-48);
if(diff<min){n=a[j];min=diff;}
}
}
cout<<n;
for(z=i-1;z<len;z++)
{
temp[u]=a[z];
u++;
}
temp[u]='\0';
sort(temp,temp+strlen(temp));
for(z=0;z<strlen(temp);z++){if(temp[z]==n&&f==0){f=1;continue;}cout<<temp[z];}
}
return 0;
}
你可以用O(n)(其中n是位数)这样做:
从右边开始，找到左位数小于右位数的第一对数字。让我们用“digit-x”来表示左边的数字。在数字-x的右边找到比数字-x大的最小的数，并把它放在数字-x的左边。最后，按升序对剩余的数字进行排序——因为它们已经是降序的，所以你所需要做的就是将它们颠倒(除了digit-x，它可以放在O(n)中正确的位置)。
举个例子可以更清楚地说明这一点:
123456784987654321
start with a number
123456784 987654321
^the first place from the right where the left-digit is less than the right
Digit "x" is 4
123456784 987654321
^find the smallest digit larger than 4 to the right
123456785 4 98764321
^place it to the left of 4
123456785 4 12346789
123456785123446789
^sort the digits to the right of 5. Since all of them except
the '4' were already in descending order, all we need to do is
reverse their order, and find the correct place for the '4'
正确性证明:
让我们用大写字母来定义数字字符串，用小写字母来定义数字。语法AB表示“字符串A和B的连接”。<是字典排序，当数字字符串长度相等时，它与整数排序相同。
原始数N是AxB的形式，其中x是个位数，B是降序的。 我们的算法找到的数字是AyC，其中y∈B是最小的数字> x(由于x的选择方式，它必须存在，见上文)，C是升序排序的。
假设有一些数字(使用相同的数字)N'使得AxB < N' < AyC。N'必须以A开头，否则它不可能在它们之间，所以我们可以把它写成AzD的形式。现在我们的不等式是AxB < AzD < AyC，它等价于xB < zD < yC，其中所有三个数字字符串都包含相同的数字。
为了使它成立，我们必须有x <= z <= y，因为y是最小的数字> x, z不能在它们之间，所以z = x或z = y，假设z = x，那么我们的不等式是xB < xD < yC，这意味着B和D都有相同的数字。但是，B是降序的，所以没有比它大的数字的字符串。因此，我们不能让B < D，按照同样的步骤，我们可以看到，如果z = y，我们不能让D < C。
因此N'不存在，这意味着我们的算法正确地找到了下一个最大的数字。
int t,k,num3,num5;
scanf("%d",&t);
int num[t];
for(int i=0;i<t;i++){
scanf("%d",&num[i]);
}
for(int i=0;i<t;i++){
k=(((num[i]-1)/3)+1);
if(k<0)
printf("-1");
else if(num[i]<3 || num[i]==4 || num[i]==7)
printf("-1");
else{
num3=3*(2*num[i] - 5*k);
num5=5*(3*k -num[i]);
for(int j=0;j<num3;j++)
printf("5");
for(int j=0;j<num5;j++)
printf("3");
}
printf("\n");
}
关于如何做到这一点，请参阅Knuth的“计算机编程艺术:生成所有排列”(.ps.gz)中的“算法L”。
