我刚刚搞砸了一次面试，而且我的面试问题几乎毫无进展。
给定一个数，找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定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));
}
其他回答
你可以用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'不存在，这意味着我们的算法正确地找到了下一个最大的数字。
我只测试了两个数字。他们工作。 在去年12月退休之前，我做了8年的IT经理，我关心三件事: 1)准确性:如果它总是有效，那就很好。 2)速度:用户可以接受。 3)明确:我可能没有你聪明，但我付你薪水。确保你用英语解释你在做什么。
奥马尔，祝你好运。
Sub Main()
Dim Base(0 To 9) As Long
Dim Test(0 To 9) As Long
Dim i As Long
Dim j As Long
Dim k As Long
Dim ctr As Long
Const x As Long = 776914648
Dim y As Long
Dim z As Long
Dim flag As Boolean
' Store the digit count for the original number in the Base vector.
For i = 0 To 9
ctr = 0
For j = 1 To Len(CStr(x))
If Mid$(CStr(x), j, 1) = i Then ctr = ctr + 1
Next j
Base(i) = ctr
Next i
' Start comparing from the next highest number.
y = x + 1
Do
' Store the digit count for the each new number in the Test vector.
flag = False
For i = 0 To 9
ctr = 0
For j = 1 To Len(CStr(y))
If Mid$(CStr(y), j, 1) = i Then ctr = ctr + 1
Next j
Test(i) = ctr
Next i
' Compare the digit counts.
For k = 0 To 9
If Test(k) <> Base(k) Then flag = True
Next k
' If no match, INC and repeat.
If flag = True Then
y = y + 1
Erase Test()
Else
z = y ' Match.
End If
Loop Until z > 0
MsgBox (z), , "Solution"
End Sub
function foo(num){
sortOld = num.toString().split("").sort().join('');
do{
num++;
sortNew = num.toString().split("").sort().join('');
}while(sortNew!==sortOld);
return num;
}
#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;
}
这里是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));
}
推荐文章
- 给定一个数字，找出下一个与原始数字具有完全相同的数字集的更高的数字
- HSL到RGB的颜色转换
- 使用Java在原语数组中查找最大/最小值
- 好的Java图算法库?
- 什么时候我应该使用Kruskal而不是Prim(反之亦然)?
- 取一个集中在中心的随机数
- 如何计算圆周长上的一点?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下，您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
- 如何使用JavaScript比较软件版本号?数量(只)
- 跳跃表vs.二叉搜索树
- 如何使四舍五入百分比加起来为100%
- 是否有可能得到一个函数的所有参数作为单一对象内的函数?
- LL和LR解析之间的区别是什么?
