给定一个数字，找到下一个更大的数字，该数字与原始数字具有完全相同的数字集

  • Z时代
  • 2024-01-10
  • 分类：问答

我只是轰炸了一次采访，在采访问题上取得了几乎零进展。谁能让我知道该怎么做？我尝试在线搜索，但找不到任何内容：

给定一个数字，找到下一个更大的数字，该数字与原始数字具有完全相同的数字集。例如：给定38276返回38627

我想从找到小于该位数的第一个数字的索引开始（从右边开始）。然后，我将轮换子集中的最后一个数字，以使其成为由相同数字组成的下一个最大数字，但卡住了。

面试官还建议尝试一次交换一位数字，但我无法弄清楚算法，只能盯着屏幕看20到30分钟。不用说，我认为我将不得不继续寻找工作。

编辑：出于什么价值，我被邀请参加下一轮采访

回答：

您可以这样输入O(n)（n位数是）：

从右边开始，找到第一个数字对，以使左边的数字小于右边的数字。让我们用“ digit-x”来指代左数字。在数字-x的右边找到大于数字-

x的最小数字，并将其放在数字-x的左侧。最后，将其余数字按升序排序-由于它们已经按 降序 排列，因此您要做的就是将它们反转

（保存digit-x，可以将其放置在中的正确位置O(n)）。

一个示例将使这一点更加清楚：

123456784987654321
以数字开头
123456784 987654321
         ^左数小于右数的从右到右的第一位  
         数字“ x”为4
123456784 987654321
              ^在右侧找到大于4的最小数字
123456785 4 98764321
        ^将其放在4的左侧
123456785 4 12346789
123456785123446789
         ^将数字右边的5排序。因为除 
         “ 4”已经按降序排列，我们要做的就是 
         颠倒顺序，找到正确的'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与D具有相同的数字。然而，B是降序排序，所以

是 没有字符串与比它大的数字。因此我们不能拥有B < D。遵循相同的步骤，我们看到if z = y不能拥有D < C。

因此N'不存在，这意味着我们的算法正确找到了下一个最大的数字。

以上是 给定一个数字，找到下一个更大的数字，该数字与原始数字具有完全相同的数字集 的全部内容， 来源链接： utcz.com/qa/428968.html

回到顶部