仅使用允许的数字构建大于 K 的最小数字

Question

给定一个包含 0-9 和数字 K 之间的数字的数组，找到由数组中的数字组成的最小数字，使其大于 K

例如，如果array = [0,1]和K = 21，程序应该return100，如0、1和10小于21，100是第一个只由zeros和ones组成的大于21的数。

我可以考虑暴力法，我可以找到所有可以用数组中的数字创建的可能数字，然后找到大于 K 的最小数字，但我正在寻找更聪明和优雅的解决方案。你有什么建议吗？

Answer 1

你能建立一个等于给定数字的数字，除了最后一个数字更大，是吗？

不是吗？那么，除了十位数大一点，你能不能造出一个和给定的数相等的数？

等等...

Answer 2

算法：

让我介绍一些变量：

k_digits-数字中的位数K.

首先，我们可以观察到我们得到的数字会有k_digits或k_digits + 1。如果还不清楚，我会在最后详细解释。

让我们从假设答案将有 k_digit 位开始。

我们可以将主要问题拆分成几个较小的问题（然后通过组合子问题的解决方案来得到初始问题的答案）。子问题的表述如下：

What is the smallest number is larger than K WITHOUT last digit.

Can we compose the number K without last digit from the digits we are allowed to use?

假设我们有解决这两个问题的方法。然后我们需要找到初始问题的答案。我们可以通过以下方式做到这一点：

a) 如果子问题2的答案为真（我们可以不带最后一位进行组合）。然后我们应该尝试将集合中的最小可用数字添加到该数字的末尾，使其大于 K。我们实际做的 - 我们尝试用 allowed set 中较大的数字替换初始 K 的最后一位。我们称此为 新号码 answer1.

b) 将集合中的最小可用数字添加到第一个子问题的数字末尾。该数字将大于 K，因为它的前缀更大。我们称这个号码为 answer2.

c) 在最后一步，我们应该比较 answer1（如果存在）和 answer2，并选择最小的。这将是最初问题的答案。

好吧，现在我希望清楚我们如何组合子问题的答案。所以，现在我将解释如何找到子问题的解决方案。

让我们从第二个子问题开始。这很简单 - 我们只需检查 allowed set 中是否包含号码 K 的所有数字（没有最后一位）。

现在是第一个子问题。您可能会注意到此子问题等于初始问题，但 K 更小。所以，我们可以解决这个"recursively"。这里的基本情况是个位数 K。当我们只有一个数字时，我们可以直接说出答案 - 只需在我们的集合中搜索比 K.

的数字更大的数字

另外，请注意，在某些时候我们可能没有子问题 1 的答案。这意味着我们无法组合长度 k_digits 大于 K 的数字。但是，在这种情况下，我们总是可以用 k_digits + 1 组合数字。只需 select 允许集合中的最小数字 (k_digits + 1) 次。 特例：零。

示例：

allowed_set=[4,5]
K = 435

我们可以看到我们可以将初始问题分解为子问题，其中 K = 43。第二个子问题的解决方案是 false，因为我们不允许使用数字 3。我们将尝试通过以下方式找到第一个子问题的解决方案 - 将其再次拆分为两个子问题，其中 K = 4。在这种情况下，第一个子问题的答案将是 5，而第二个子问题的答案将是 4。我们可以将案例 K = 43 的答案组成如下：answer1 = 44、answer2 = 54。 answer1 较小，因此，这实际上是 K = 43 情况的答案。然后，要找到 K = 435 的答案，我们只能将 4 添加到 44 的末尾。所以，答案是444。

这可能不是最好的例子，但我希望它能说明我的答案。询问，如果您有任何其他意见。

Answer 3

我自己在编程方面还很陌生，大约有 4 个月的 C++ 经验，我们被分配了一个与此非常相似的作业作为我们的作业问题之一，希望这对您有所帮助！

//given array A of usable digits and assuming it is sorted
//meaning A[1] is the smallest

ans = 0;

//first we find the digits of K
//we use {} as Gauss
K_digits = {log(K)} + 1
numleft = K;
for i = 1 to K_digits
    B[i] = {numleft/(10^(K_digits - i))}
    numleft = numleft - B[i]*10^(K_digits - i)

//next we search through the array K_digits times
Max_seq = A[A.length] // max number in array
min_seq = A[1] // min number in array
usebigger = 0  // if this equals 1, we need to add an extra digit than K to be larger than K
copy = 0 //number of digits to copy, starting from left side

j = 1
while (j <= K_digits)
    if Max_seq < B[j]
        usebigger = 1
        j = K_digits + 1 // end while loop
    else if Max_seq == B[j]
        copy = copy + 1
        j = j + 1
    else if Max_seq > B[j] 
        for t = 1 to A.length
            if B[j] < A[t]
            value = A[t]
            break;
        j = K_digits + 1

if copy == K_digits // can only manage to find a same valued number
    usebigger = 1


//finally, with this info, we find the answer
if usebigger == 1 // need to add an extra digit than K to be larger than K
    if min_seq == 0
        for s = 1 to A.length
            if A[s] > 0
            min_num = A[S]
            break;
        ans = min_num*(10^K_digits)
    else
        for x = 0 to K_digits
            ans = ans + min_seq*(10^x)    

else
    if copy != 0
        for i = 1 to copy
            ans = ans + B[i]*(10^(K_digits - i))
    ans = ans + value*(10^(K_digits - copy - 1))

    if copy+2 <= K_digits
        for y = copy+2 to K_digits
            ans = ans + min_seq*(10^(K_digits - y))

return ans

仅使用允许的数字构建大于 K 的最小数字

Build smallest number larger than K using only allowed digits

algorithm

language-agnostic