给定一个目标数 n，给定一组数组 nums，求由 nums 组成的比 n 小的最大数。

示例 1：

输入：n = 23112, nums = [2, 4, 9]
输出：0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package main  
  
import (  
   "fmt"  
   "sort"   "strconv")  
  
func findMaxLessThanN(target int, nums []int) (result int) {  
   targetStr := strconv.Itoa(target)  
   var targetNums []int  
   for i, _ := range targetStr {  
      targetNums = append(targetNums, int(targetStr[i]-'0'))  
   }  
  
   // Sort A in descending order  
   sort.Sort(sort.Reverse(sort.IntSlice(nums)))  
   ASet := make(map[int]bool)  
   for _, a := range nums {  
      ASet[a] = true  
   }  
   length := len(targetNums)  
  
   for i := 0; i < length; i++ {  
      currentDigit := targetNums[i]  
      largestLess, found := findLargestLessThan(currentDigit, nums)  
  
      if found {  
         // Replace the current digit with the largest less than itself  
         targetNums[i] = largestLess  
         // Fill the rest of the digits with the largest in A  
         for j := i + 1; j < length; j++ {  
            targetNums[j] = nums[0]  
         }  
         break  
      } else if !ASet[currentDigit] {  
         // If current digit is not in A and we cannot find a smaller digit, backtrack  
         for i >= 0 && !ASet[targetNums[i]] {  
            i--  
         }  
  
         if i < 0 {  
            // If no valid digit was found, return the largest possible number with one less digit  
            result := 0  
            for j := 0; j < length-1; j++ {  
               result = result*10 + nums[0]  
            }  
            return result  
         }  
  
         // Replace the found digit with the largest less than itself and fill the rest  
         largestLess, _ = findLargestLessThan(targetNums[i], nums)  
         targetNums[i] = largestLess  
         for j := i + 1; j < length; j++ {  
            targetNums[j] = nums[0]  
         }  
         break  
      }  
   }  
  
   // Convert the runes back to an integer  
   for _, n := range targetNums {  
      result = result*10 + n  
   }  
   return result  
}  
  
// findLargestLessThan finds the largest digit in A that is less than the given digitfunc findLargestLessThan(digit int, A []int) (int, bool) {  
   for _, a := range A {  
      if a < digit {  
         return a, true  
      }  
   }  
   return 0, false  
}  
  
func main() {  
   n := 23121  
   A := []int{2, 4, 9}  
   fmt.Println(findMaxLessThanN(n, A)) // Output: 22999  
}

详细解释

  1. findLargestLessThan: 一个辅助函数，用于找到集合 A 中小于给定数字的最大数字。
  2. findMaxLessThanN: 主要函数，根据给定数字 n 和集合 A，逐位处理，找到满足条件的最大数字。
    • 将 n 转换为字符串以便逐位处理。
    • 对集合 A 进行排序，并构建一个快速查找的集合 ASet。
    • 从高位开始逐位处理 n，如果找到可以替换的数字则进行替换，并将后续位设为集合 A 中最大的数字。
    • 如果无法替换当前位，进行回溯处理，找到可以替换的前一位。