给定一个号码，找到下一个较高数具有完全相同的一组数字的原始数 [英] Given a number, find the next higher number which has the exact same set of digits as the original number

问题描述

我刚刚轰炸的采访，并在我的采访问题上取得pretty的很多零的进步。任何人都可以让我知道如何做到这一点？我试着在网上搜索，但没有找到任何东西：

I just bombed an interview and made pretty much zero progress on my interview question. Can anyone let me know how to do this? I tried searching online but couldn't find anything:

给定一个号码，找到下一个较高数具有完全相同的   设置的数字作为原始号码。例如：给定的38276回报   38627

Given a number, find the next higher number which has the exact same set of digits as the original number. For example: given 38276 return 38627

我想要开始通过找到的第一个数字的，这是小于的个位的索引（从右侧）。然后我会旋转的最后数字的子集，它是由相同数字的下一个大数目，但卡住了。

I wanted to begin by finding the index of the first digit (from the right) that was less than the ones digit. Then I would rotate the last digits in the subset such that it was the next biggest number comprised of the same digits, but got stuck.

面试官还建议尝试换一次数字之一，但我无法弄清楚的算法，只是盯着像20-30分钟的画面。不用说，我想我将不得不继续找工作。

The interviewer also suggested trying to swap digits one at a time, but I couldn't figure out the algorithm and just stared at a screen for like 20-30 minutes. Needless to say, I think I'm going to have to continue the job hunt.

编辑：什么它的价值，我被邀请参加下一轮面试

edit: for what its worth, I was invited to the next round of interviews

推荐答案

您可以做到这一点在 O（N）（其中 N 是的位数）是这样的：

You can do it in O(n) (where n is the number of digits) like this:

从右边开始，你会发现第一对- - 数字，它的左边位比右位小。让我们参阅左位由数字-X。找到比数字-X为数字-x的右侧较大的最小数，并把它立即离开数字-X的。最后，以升序排序其余数字 - 因为他们已经在降的顺序，所有你需要做的是扭转他们的（保存为数字-X，它可以放置在正确发生在 O（N））的。

Starting from the right, you find the first pair-of-digits such that the left-digit is smaller than the right-digit. Let's refer to the left-digit by "digit-x". Find the smallest number larger than digit-x to the right of digit-x, and place it immediately left of digit-x. Finally, sort the remaining digits in ascending order - since they were already in descending order, all you need to do is reverse them (save for digit-x, which can be placed in the correct place in O(n)).

这是例子使这更清楚：

123456784987654321
start with a number

123456784 987654321
         ^the first place where the left-digit is less-than the right-digit is here.  
         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'

这篇关于给定一个号码，找到下一个较高数具有完全相同的一组数字的原始数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！