字节面试高频题解析：贪心+二分法寻找小于n的最大数

1. 问题背景与核心思路

这道题目要求我们从给定的数字数组中组合出小于目标数n的最大数字。数字可以重复使用，且组合结果需要尽可能接近n。例如，给定nums=[2,8,8,6,7]，n=88888时，最优解是88887。

贪心算法的核心思想 在于：从最高位开始，尽可能匹配n的每一位数字。当无法完全匹配时，选择比当前位稍小的数字，后续位则填充最大可用数字。这种策略能保证我们找到的是"最接近n"的解。

二分法的应用场景 出现在我们需要快速定位数组中满足特定条件的元素时。在本问题中，我们需要在已排序的nums中找到小于等于目标值的最大数字，这正是二分查找的典型应用。

2. 算法实现详解

2.1 预处理阶段

首先需要对输入数组进行排序，这是二分查找的前提条件：

nums.sort()  # 升序排序便于二分查找

2.2 核心三行代码实现

以下是经过提炼的Python实现核心逻辑：

def find_max_num(nums, n):
    n_str = str(n-1)  # 转换为字符串便于逐位处理
    res = []
    for i, ch in enumerate(n_str):
        target = int(ch)
        # 二分查找小于等于target的最大数
        idx = bisect.bisect_right(nums, target) - 1
        if idx >= 0:
            res.append(str(nums[idx]))
            if nums[idx] < target:  # 后续位可填充最大值
                res.extend([str(nums[-1])]*(len(n_str)-i-1))
                break
        else:  # 当前位无合适数字，需要回溯
            return int(str(nums[-1])*(len(n_str)-1)) if len(n_str)>1 else -1
    return int(''.join(res)) if res else -1

2.3 性能对比分析

方法	时间复杂度	空间复杂度	适用场景
回溯法	O(k^m)	O(m)	小规模数据，需要所有解
贪心+二分法	O(mlogk)	O(m)	大规模数据，最优解

其中：

• m为数字n的位数
• k为nums数组的长度

3. 面试考察要点

这道题目在字节跳动面试中出现频率较高，主要考察以下几个维度：

1. 算法设计能力 ：能否识别问题本质并选择合适的算法组合

2. 编码实现能力 ：能否将算法思路转化为简洁高效的代码

3. 边界处理能力 ：是否考虑到各种特殊情况：

   • nums中所有数字都大于n的某一位
   • n比nums能组成的最小数字还小
   • 数字可重复使用的处理

4. 性能分析能力 ：能否正确分析算法复杂度并比较不同解法

4. 常见变体与扩展

在实际面试中，可能会遇到以下变体问题：

1. 不可重复使用数字 ：需要修改组合策略，记录已使用数字
2. 包含0的情况 ：需要特别处理首位不能为0的限制
3. 多解要求 ：可能需要返回所有接近的解而不仅最大解
4. 组合数统计 ：改为统计小于n的所有可能组合数量

# 变体示例：不可重复使用数字
def find_max_num_no_repeat(nums, n):
    nums.sort()
    n_str = str(n-1)
    used = [False]*len(nums)
    # ...修改选择逻辑，标记已用数字...

5. 实战技巧与注意事项

1. 预处理排序 ：二分查找必须基于有序数组
2. 字符串处理技巧 ：将数字转为字符串便于逐位比较
3. 边界条件检查 ：
   • n为1位数时的特殊处理
   • nums为空或全大于n的情况
4. 测试用例设计 ：
   • 常规情况：nums=[2,4,9], n=2531 → 2499
   • 边缘情况：nums=[5,6], n=7 → 6
   • 极端情况：nums=[9], n=8 → -1

提示：面试时可以先讨论暴力解法，再逐步优化到贪心+二分法，展示思维过程

6. 相关题目推荐

为了更好掌握这类问题，建议练习以下LeetCode题目：

1. 179. 最大数（排序+自定义比较）
2. 402. 移掉K位数字（贪心+栈）
3. 738. 单调递增的数字（贪心策略）
4. 556. 下一个更大元素III（类似的全排列问题）

7. 代码优化与可读性

最终优化版本增加了一些防御性编程和注释：

import bisect

def find_max_number(nums, n):
    """
    在给定数字数组中找出小于n的最大组合数
    :param nums: List[int], 可选数字(1-9)
    :param n: int, 目标数
    :return: int, 满足条件的最大数
    """
    if not nums or n <= 0:
        return -1
    
    nums.sort()  # 升序排序便于二分
    max_digit = str(nums[-1])
    
    # 处理n-1转为字符串
    try:
        n_str = str(n-1)
    except:
        return -1
    
    result = []
    for i, ch in enumerate(n_str):
        target = int(ch)
        # 二分查找小于等于target的最大数索引
        idx = bisect.bisect_right(nums, target) - 1
        
        if idx >= 0:
            result.append(str(nums[idx]))
            # 如果当前位已经小于目标，后续可填充最大值
            if nums[idx] < target:
                result.append(max_digit * (len(n_str)-i-1))
                break
        else:
            # 无法满足当前位，需要减少位数并填充最大值
            return int(max_digit * (len(n_str)-1)) if len(n_str)>1 else -1
    
    return int(''.join(result)) if result else -1

在实际工程应用中，还可以添加输入验证、日志记录等生产级代码需要考虑的因素。