合并以获得大于目标的最小数字
Combine to get smallest num that larger than a target
我遇到一个算法问题：
给定一个数组arr（只包含一些单个数字）和一个整数K（你可以假设[=中的int类型35=]), 组合数组中的数得到大于K的最小整数。
（combine的意思就是像你可以把arr中的每一个元素都看成一个字符串，然后把它们拼接起来。比如：我用四个“1”得到“1”+“1”+“1”+“1”=“1111” )
示例：
arr: [1,2,3,4] target:123 , 输出: 124
arr: [1,2,3,4] target:999 , 输出: 1111
arr: [9] target:23 , 输出: 99
我可以想出一个蛮力的方法，使用回溯首先找到所有可能的组合，然后遍历所有候选以找到结果。
这里有优化吗？
以下一组观察结果可用于解决此问题：
- 对于
x 位目标，答案将有 x 位或 x+1 位
- 如果目标大于我们可以生成的最大
x 位数，则答案将是可能的最小 x+1 位数。 （示例：arr: [1,2,3,4], target:999, output: 1111）
- 否则，我们迭代目标的数字。对于每个数字，我们在数组中找到最接近的大于或等于该数字的整数。如果选择的数字相等，我们继续。否则，如果我们选择的数字更大，我们可以贪婪地为剩余的位置插入尽可能小的数字。
示例：arr: [1,2,4,6,9] target: 12378。遍历目标：
Digit: 1, closest value = 1 (which are equal)
Digit: 2, closest value = 2 (which are equal)
Digit: 3, closest value = 4 (which is greater)
Since we've picked a greater value now, we will pick the smallest digit for the remaining places.
Digit: 7, chosen value = 1 (which is the smallest digit we can choose)
Digit: 8, chosen value = 1 (which is the smallest digit we can choose)
Final answer = 12411
我遇到一个算法问题：
给定一个数组arr（只包含一些单个数字）和一个整数K（你可以假设[=中的int类型35=]), 组合数组中的数得到大于K的最小整数。 （combine的意思就是像你可以把arr中的每一个元素都看成一个字符串，然后把它们拼接起来。比如：我用四个“1”得到“1”+“1”+“1”+“1”=“1111” )
示例：
arr: [1,2,3,4] target:123 , 输出: 124
arr: [1,2,3,4] target:999 , 输出: 1111
arr: [9] target:23 , 输出: 99
我可以想出一个蛮力的方法，使用回溯首先找到所有可能的组合，然后遍历所有候选以找到结果。
这里有优化吗？
以下一组观察结果可用于解决此问题：
- 对于
x位目标，答案将有x位或x+1位 - 如果目标大于我们可以生成的最大
x位数，则答案将是可能的最小x+1位数。 （示例：arr: [1,2,3,4], target:999, output: 1111） - 否则，我们迭代目标的数字。对于每个数字，我们在数组中找到最接近的大于或等于该数字的整数。如果选择的数字相等，我们继续。否则，如果我们选择的数字更大，我们可以贪婪地为剩余的位置插入尽可能小的数字。
示例：arr: [1,2,4,6,9] target: 12378。遍历目标：
Digit: 1, closest value = 1 (which are equal)
Digit: 2, closest value = 2 (which are equal)
Digit: 3, closest value = 4 (which is greater)
Since we've picked a greater value now, we will pick the smallest digit for the remaining places.
Digit: 7, chosen value = 1 (which is the smallest digit we can choose)
Digit: 8, chosen value = 1 (which is the smallest digit we can choose)
Final answer = 12411