我刚刚搞砸了一次面试，而且我的面试问题几乎毫无进展。
给定一个数，找出下一个与之完全相同的更大的数 作为原始数字的数字集。例如:给定38276返回 38627
我想从找到第一个比个位小的数字的下标开始。然后我将旋转子集中的最后一个数字，这样它是由相同的数字组成的下一个最大的数字，但卡住了。
面试官还建议我试着一次换一个数字，但我搞不懂算法，只能盯着屏幕看20-30分钟。不用说，我想我还得继续找工作。
当前回答
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<string.h>
#include<sstream>
#include<iostream>
using namespace std;
int compare (const void * a, const void * b)
{
return *(char*)a-*(char*)b;
}
/*-----------------------------------------------*/
int main()
{
char number[200],temp;
cout<<"please enter your number?"<<endl;
gets(number);
int n=strlen(number),length;
length=n;
while(--n>0)
{
if(number[n-1]<number[n])
{
for(int i=length-1;i>=n;i--)
{
if(number[i]>number[n-1])
{
temp=number[i];
number[i]=number[n-1];
number[n-1]=temp;
break;
}
}
qsort(number+n,length-n,sizeof(char),compare);
puts(number);
return 0;
}
}
cout<<"sorry itz the greatest one :)"<<endl;
}
其他回答
解决方案(在Java中)可能是以下(我相信这里的朋友可以找到更好的): 从字符串的末尾开始交换数字，直到得到一个更高的数字。 也就是说，首先从下位开始移动。然后到达下一个更高的地方，直到你到达下一个更高的地方。 然后对剩下的进行排序。 在你的例子中，你会得到:
38276 --> 38267 (smaller) --> 38627 Found it
^ ^ ^
public static int nextDigit(int number){
String num = String.valueOf(number);
int stop = 0;
char [] chars = null;
outer:
for(int i = num.length() - 1; i > 0; i--){
chars = num.toCharArray();
for(int j = i; j > 0; j--){
char temp = chars[j];
chars[j] = chars[j - 1];
chars[j - 1] = temp;
if(Integer.valueOf(new String(chars)) > number){
stop = j;
break outer;
}
}
}
Arrays.sort(chars, stop, chars.length);
return Integer.valueOf(new String(chars));
}
这里是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));
}
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#中没有想到的聪明的解决方案
using System;
using System.Linq;
public static long NextBiggerNumber(long n)
{
String str = GetNumbers(n);
for (long i = n+1; i <= long.Parse(str); i++)
{
if(GetNumbers(n)==GetNumbers(i))
{
return i;
}
}
return -1;
}
public static string GetNumbers(long number)
{
return string.Join("", number.ToString().ToCharArray().OrderByDescending(x => x));
}
只是使用python的另一个解决方案:
def PermutationStep(num):
if sorted(list(str(num)), reverse=True) == list(str(num)):
return -1
ls = list(str(num))
n = 0
inx = 0
for ind, i in enumerate(ls[::-1]):
if i < n:
n = i
inx = -(ind + 1)
break
n = i
ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]
nl = ls[inx::-1][::-1]
ln = sorted(ls[inx+1:])
return ''.join(nl) + ''.join(ln)
print PermutationStep(23514)
输出:
23541
