algorithm - leetcode - single number算法




给定一个数字,找到下一个更高的数字,它与原始数字有完全相同的一组数字 (20)

我刚刚轰炸了一次采访,并在面试问题上取得了几乎零的进展。 任何人都可以让我知道如何做到这一点? 我尝试在网上搜索,但找不到任何东西:

给定一个数字,找到下一个更高的数字,它与原始数字有完全相同的一组数字。 例如:给出38276返回38627

我想首先找到第一位数字的索引(从右边开始),该数字小于个位数字。 然后我会旋转子集中的最后一个数字,使它成为由相同数字组成的下一个最大数字,但被卡住了。

面试官还建议尝试每次换一位数字,但我无法弄清楚算法,只是盯着屏幕20-30分钟。 不用说,我想我将不得不继续寻找工作。

编辑:为了它的价值,我被邀请参加下一轮采访


@ BlueRaja算法的JavaScript实现。

var Bar = function(num){ 
  num = num.toString();
  var max = 0;
  for(var i=num.length-2; i>0; i--){
    var numArray = num.substr(i).split("");
    max = Math.max.apply(Math,numArray);
    if(numArray[0]<max){
        numArray.sort(function(a,b){return a-b;});
        numArray.splice(-1);
        numArray = numArray.join("");
        return Number(num.substr(0,i)+max+numArray);
    }
  }
  return -1;
};

Very simple implementation using Javascript, next highest number with same digits

/*
Algorithm applied
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.

III) Swap the above found two digits, we get 536974 in above example.

IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.

*/

function findNext(arr)
{
  let i;
  //breaking down a digit into arrays of string and then converting back that array to number array
  let arr1=arr.toString().split('').map(Number) ;
  //started to loop from the end of array 
  for(i=arr1.length;i>0;i--)
  {
    //looking for if the current number is greater than the number next to it
    if(arr1[i]>arr1[i-1])
    {// if yes then we break the loop it so that we can swap and sort
      break;}
  }

  if(i==0)
  {console.log("Not possible");}

   else
  {
   //saving that big number and smaller number to the left of it
   let smlNum =arr1[i-1];
    let bigNum =i;
   /*now looping again and checking if we have any other greater number, if we have one AFTER big number and smaller number to the right. 
     A greater number that is of course greater than that smaller number but smaller than the first number we found.
     Why are doing this? Because that is an algorithm to find next higher number with same digits. 
   */
    for(let j=i+1;j<arr1.length;j++)
      {//What if there are no digits afters those found numbers then of course loop will not be initiated otherwise...
        if(arr1[j]> smlNum && arr1[j]<arr1[i])
        {// we assign that other found number here and replace it with the one we found before
          bigNum=j;

        }
      } //now we are doing swapping of places the small num and big number , 3rd part of alogorithm
    arr1[i-1]=arr1[bigNum];
          arr1[bigNum]=smlNum;
    //returning array 
    //too many functions applied sounds complicated right but no, here is the  trick
    //return arr first then apply each function one by one to see output and then further another func to that output to match your needs
    // so here after swapping , 4th part of alogorithm is to sort the array right after the 1st small num we found
    // to do that first we simple take part of array, we splice it and then we apply sort fucntion, then check output (to check outputs, pls use chrome dev console)
    //and then  simply the rest concat and join to main one digit again.
     return arr1.concat((arr1.splice(i,arr1.length)).sort(function(a, b){return a-b})).join('');



    // Sorry to make it too long but its fun explaining things in much easier ways as much as possible!!
  }

}


findNext(1234);

Since there are lot of comments, so it's better you can copy it to your text editor. 谢谢!


I know this is very old question but still I didn't find easy code in c#. This might help guys who are attending interviews.

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

一个几乎相同的问题出现在Code Jam问题中,并且有一个解决方案:

http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1

以下是使用示例的方法摘要:

34722641

A.将数字序列拆分为两部分,以便在保持降序的同时尽可能长地保留右部分:

34722 641

(如果整个号码的顺序是递减的,没有更大的号码可以不添加数字。)

B.1。 选择第一个序列的最后一位数字:

3472(2) 641

B.2。 找到第二个序列中比它大的最小数字:

3472(2) 6(4)1

B.3。 交换他们:

3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621

C.按递增顺序排序第二个序列:

34724 126

D.完成!

34724126

下面是生成一个数字的所有排列的代码..虽然必须首先使用String.valueOf(整数)将该整数转换为字符串。

/**
 * 
 * Inserts a integer at any index around string.
 * 
 * @param number
 * @param position
 * @param item
 * @return
 */
public String insertToNumberStringAtPosition(String number, int position,
        int item) {
    String temp = null;
    if (position >= number.length()) {
        temp = number + item;
    } else {
        temp = number.substring(0, position) + item
                + number.substring(position, number.length());
    }
    return temp;
}

/**
 * To generate permutations of a number.
 * 
 * @param number
 * @return
 */
public List<String> permuteNumber(String number) {
    List<String> permutations = new ArrayList<String>();
    if (number.length() == 1) {
        permutations.add(number);
        return permutations;
    }
    // else
    int inserterDig = (int) (number.charAt(0) - '0');
    Iterator<String> iterator = permuteNumber(number.substring(1))
            .iterator();
    while (iterator.hasNext()) {
        String subPerm = iterator.next();
        for (int dig = 0; dig <= subPerm.length(); dig++) {
            permutations.add(insertToNumberStringAtPosition(subPerm, dig,
                    inserterDig));
        }
    }
    return permutations;
}

你的想法

我想首先找到第一位数字的索引(从右边开始),该数字小于个位数字。 然后我会旋转子集中的最后一个数字,使它成为由相同数字组成的下一个最大数字,但被卡住了。

实际上,这很不错。 您不仅需要考虑最后一位数字,而且还要考虑所有数字的重要性低于当前考虑的数字。 因为在此之前,我们有一个单调的数字序列,这是最右边的数字小于其右边的邻居。 看待

1234675
    ^

具有相同数字的下一个较大数字是

1234756

找到的数字被交换为最后一位数字 - 所考虑数字中的最小数字 - 并且其余数字按升序排列。


另一个使用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

在回答这个问题时,我对蛮力算法一无所知,所以我从另一个角度来讨论它。 我决定从number_given + 1到可用的最大数字(3位数字为999,4位数字为9999等)搜索可能重新排列的可能解决方案的整个范围。 我这样做就像找到一个带有单词的回文,通过对每个解决方案的数字进行排序并将其与作为参数给出的排序数字进行比较。 然后,我简单地返回解决方案阵列中的第一个解决方案,因为这将是下一个可能的值。

这是我在Ruby中的代码:

def PermutationStep(num)

a = []
(num.to_s.length).times { a.push("9") }
max_num = a.join('').to_i
verify = num.to_s.split('').sort
matches = ((num+1)..max_num).select {|n| n.to_s.split('').sort == verify }

if matches.length < 1
  return -1
else
  matches[0]
end

结束


将9添加到给定的n位数字。 然后检查它是否在限制范围内(第一个(n + 1)位数)。 如果是,则检查新号码中的数字是否与原始号码中的数字相同。 重复添加9直到两个条件都成立。 当数字超出限制时停止算法。

我无法为这种方法提出矛盾的测试案例。


您可以在O(n) (其中n是数字的位数)中这样做:

从右侧开始,您会找到第一对数字,左侧数字小于右侧数字。 让我们用“digit-x”来指代左边的数字。 在digit-x的右侧找到大于digit-x的最小数字,并将其放在digit-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 ,其中AyC是最小的数字> x (它必须存在,因为选择x的方式,见上面)C按升序排序。

假设有一些数字(使用相同的数字) N' ,使得AxB < N' < AyCN'必须以A开始,否则它不能落在它们之间,所以我们可以以AzD的形式写出它。 现在我们的不等式是AxB < AzD < AyC ,它等于xB < zD < yC ,其中所有三个数字字符串包含相同的数字。

为了使其成立,我们必须有x <= z <= y 。 由于y是最小的数字> x ,因此z不能位于它们之间,因此z = xz = y 。 说z = x 。 那么我们的不等式是xB < xD < yC ,这意味着B < D ,其中BD具有相同的数字。 但是,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

我相当肯定你的面试官正试图轻轻推动你这样的事情:

local number = 564321;

function split(str)
    local t = {};
    for i = 1, string.len(str) do
        table.insert(t, str.sub(str,i,i));
    end
    return t;
end

local res = number;
local i = 1;
while number >= res do
    local t = split(tostring(res));
    if i == 1 then
        i = #t;
    end
    t[i], t[i-1] = t[i-1], t[i];
    i = i - 1;
    res = tonumber(table.concat(t));
end

print(res);

不一定是最高效或优雅的解决方案,但它可以在两个周期内解决所提供的示例,并像他建议的那样每次交换一位数字。


有很多很好的答案,但我没有找到一个体面的Java实现。 这是我的两分钱:

public void findNext(int[] nums) {
    int i = nums.length - 1;
    // nums[i - 1] will be the first non increasing number
    while (i > 0 && nums[i] <= nums[i - 1]) {
        i--;
    }
    if (i == 0) {
        System.out.println("it has been the greatest already");
    } else {
        // Find the smallest digit in the second sequence that is larger than it:
        int j = nums.length - 1;
        while (j >= 0 && nums[j] < nums[i - 1]) {
            j--;
        }
        swap(nums, i - 1, j);
        Arrays.sort(nums, i, nums.length);
        System.out.println(Arrays.toString(nums));
    }
}

public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

至少,下面是几个基于字符串的强力解决方案示例,您应该能够从头开始思考:

38276排序的数字列表是23678

38627排序的数字列表是23678

蛮力增量,排序和比较

沿着蛮力解决方案将被转换为一个字符串和蛮力使用这些数字所有可能的数字。

在它们全部中创建ints,将它们放入列表中并对其进行排序,获取目标条目之后的下一个条目。

如果你花了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

这是我的代码,它是这个例子的一个修改版本

图书馆:

class NumPermExample
{
    // print N! permutation of the characters of the string s (in order)
    public  static void perm1(String s, ArrayList<String> perm)
    {
        perm1("", s);
    }

    private static void perm1(String prefix, String s, ArrayList<String> perm)
    {
        int N = s.length();
        if (N == 0)
        {
            System.out.println(prefix);
            perm.add(prefix);
        }
        else
        {
            for (int i = 0; i < N; i++)
                perm1(prefix + s.charAt(i), s.substring(0, i)
                    + s.substring(i+1, N));
        }

    }

    // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s, ArrayList<String> perm)
    {
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n, ArrayList<String> perm)
    {
        if (n == 1)
        {
            System.out.println(a);
            perm.add(new String(a));
            return;
        }

        for (int i = 0; i < n; i++)
        {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }  

    // swap the characters at indices i and j
    private static void swap(char[] a, int i, int j)
    {
        char c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }

    // next higher permutation
    public static int nextPermutation (int number)
    {
        ArrayList<String> perm = new ArrayList<String>();

        String cur = ""+number;

        int nextPerm = 0;

        perm1(cur, perm);

        for (String s : perm)
        {
            if (Integer.parseInt(s) > number
                        && (nextPerm == 0 ||
                            Integer.parseInt(s) < nextPerm))
            {
                nextPerm = Integer.parseInt(s);
            }
        }

            return nextPerm;
    }
}

测试:

public static void main(String[] args) 
{
    int a = 38276;

    int b = NumPermExample.nextPermutation(a);

    System.out.println("a: "+a+", b: "+b);
}

这里有一个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://.com/a/9243091/1149664 : https://.com/a/9243091/1149664 (它与itertools中的算法相同)

以下是Weeble和BlueRaja描述的最佳答案实现 (其他答案)。 我怀疑还有什么更好的。

def findnext(ii):
    iis=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)))))

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

function foo(num){
 sortOld = num.toString().split("").sort().join('');
 do{
    num++;
   sortNew = num.toString().split("").sort().join('');
 }while(sortNew!==sortOld);
 return num;
}

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");
}






algorithm