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

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

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

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


当前回答

PHP代码

function NextHigherNumber($num1){
$num = strval($num1);
$max = 0;
for($i=(strlen($num)-2); $i>=0; $i--){
    $numArrayRaw = substr($num, $i);
    $numArray = str_split($numArrayRaw);
    $max = max($numArray);
    if ($numArray[0] < $max){
        sort( $numArray, SORT_NUMERIC );
        array_pop($numArray);
        $numarrstr = implode("",$numArray);
        $rt = substr($num,0,$i) . $max . $numarrstr;
        return $rt;
    }
}
return "-1";
}
echo NextHigherNumber(123);

其他回答

#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;
}
#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;
}

至少,这里有几个基于字符串的暴力解决方案的例子,你应该能够马上想到:

38276中的数字排序为23678

38627排序的数字列表是23678

蛮力增量,排序和比较

沿着蛮力解决方案将转换为字符串 然后用这些数字强行找出所有可能的数字。

从它们中创建int,把它们放在一个列表中并排序, 获取目标条目之后的下一个条目。

如果你花了30分钟在这个问题上,却没有想出一个蛮力的方法,我也不会雇用你。

在商业世界中,一个不优雅、缓慢和笨拙但能完成工作的解决方案总是比没有解决方案更有价值,事实上,这几乎描述了所有不优雅、缓慢和笨拙的商业软件。

这是个很有趣的问题。

这是我的java版本。在我检查其他贡献者的评论之前,从弄清楚模式到完全完成代码,我花了大约3个小时。很高兴看到我的想法和别人一样。

O (n)的解决方案。老实说,如果时间只有15分钟,并且要求在白板上完成完整的代码,我将会失败。

以下是我的解决方案的一些有趣点:

避免任何排序。 完全避免字符串操作 实现O(logN)空间复杂度

我在代码中添加了详细注释,并在每个步骤中添加了大O。

  public int findNextBiggestNumber(int input  )   {
    //take 1358642 as input for example.
    //Step 1: split the whole number to a list for individual digital   1358642->[2,4,6,8,5,3,1]
    // this step is O(n)
    int digitalLevel=input;

    List<Integer> orgNumbersList=new ArrayList<Integer>()   ;

    do {
        Integer nInt = new Integer(digitalLevel % 10);
        orgNumbersList.add(nInt);

        digitalLevel=(int) (digitalLevel/10  )  ;


    } while( digitalLevel >0)    ;
    int len= orgNumbersList.size();
    int [] orgNumbers=new int[len]  ;
    for(int i=0;i<len;i++){
        orgNumbers[i ]  =  orgNumbersList.get(i).intValue();
    }
    //step 2 find the first digital less than the digital right to it
    // this step is O(n)


    int firstLessPointer=1;
    while(firstLessPointer<len&&(orgNumbers[firstLessPointer]>orgNumbers[ firstLessPointer-1 ])){
        firstLessPointer++;
    }
     if(firstLessPointer==len-1&&orgNumbers[len-1]>=orgNumbers[len-2]){
         //all number is in sorted order like 4321, no answer for it, return original
         return input;
     }

    //when step 2 step finished, firstLessPointer  pointing to number 5

     //step 3 fristLessPointer found, need to find  to  first number less than it  from low digital in the number
    //This step is O(n)
    int justBiggerPointer=  0 ;

    while(justBiggerPointer<firstLessPointer&& orgNumbers[justBiggerPointer]<orgNumbers[firstLessPointer]){
        justBiggerPointer++;
    }
    //when step 3 finished, justBiggerPointer  pointing to 6

    //step 4 swap the elements  of justBiggerPointer and firstLessPointer .
    // This  is O(1) operation   for swap

   int tmp=  orgNumbers[firstLessPointer] ;

    orgNumbers[firstLessPointer]=  orgNumbers[justBiggerPointer]  ;
     orgNumbers[justBiggerPointer]=tmp ;


     // when step 4 finished, the list looks like        [2,4,5,8,6,3,1]    the digital in the list before
     // firstLessPointer is already sorted in our previous operation
     // we can return result from this list  but  in a differrent way
    int result=0;
    int i=0;
    int lowPointer=firstLessPointer;
    //the following pick number from list from  the position just before firstLessPointer, here is 8 -> 5 -> 4 -> 2
    //This Operation is O(n)
    while(lowPointer>0)        {
        result+= orgNumbers[--lowPointer]* Math.pow(10,i);
        i++;
    }
    //the following pick number from list   from position firstLessPointer
    //This Operation is O(n)
    while(firstLessPointer<len)        {
        result+= orgNumbers[firstLessPointer++ ]* Math.pow(10,i);
        i++;
    }
     return  result;

}

下面是在Intellj中运行的结果:

959879532-->959892357
1358642-->1362458
1234567-->1234576
77654321-->77654321
38276-->38627
47-->74
#include <iostream>
using namespace std;

int main ()
{
  int num=15432;
  int quot,rem;
  int numarr[5];
  int length=0;
  while(num!=0)
  {
      rem=num%10;
      num = num/10;
      numarr[length]=rem;
      length++;
  }

 for(int j=0;j<length;j++)
  {
  for(int i=0;i<length;i++)
  {
      if(numarr[i]<numarr[i+1])
      {
          int tmp=numarr[i];
          numarr[i]=numarr[i+1];
          numarr[i+1]=tmp;
      }
  }
  }

  for(int j=0;j<length;j++)
  {
   cout<<numarr[j];
  }
  return 0;
}