面试题：Python多列表条件判断下的高效算法优化

Question

有多个列表（列表数量不定，以列表的列表形式传入，例如 [[1, 2, 3], [4, 5, 6], [7, 8, 9]]），每个列表中的元素都是正整数。要求编写一个高效的Python函数，判断是否存在一种组合，从每个列表中取一个元素，使得这些取出元素的乘积能被10整除。请考虑如何优化算法，减少不必要的计算，尤其是在列表数量较多和列表元素较多的情况下，并给出算法时间复杂度分析。

Answer 1

def can_product_be_divisible_by_10(lists):
    has_5 = False
    has_even = False
    for sublist in lists:
        has_5_in_sublist = False
        has_even_in_sublist = False
        for num in sublist:
            if num % 5 == 0:
                has_5_in_sublist = True
            if num % 2 == 0:
                has_even_in_sublist = True
        if has_5_in_sublist:
            has_5 = True
        if has_even_in_sublist:
            has_even = True
        if has_5 and has_even:
            return True
    return has_5 and has_even

算法优化思路

1. 核心原理：一个数能被10整除，当且仅当它同时含有因子2和5。因此，我们不需要枚举所有可能的组合来计算乘积，只需要判断是否存在一种组合，其中既包含能被2整除的数，又包含能被5整除的数。
2. 优化方式：
   • 遍历每个子列表，在子列表中同时寻找能被2整除的数和能被5整除的数。
   • 记录全局是否已经找到能被2整除的数和能被5整除的数。一旦全局同时找到这两种数，立即返回True。

时间复杂度分析

1. 假设：假设有 n 个列表，每个列表平均长度为 m。
2. 分析：
   • 外层循环遍历 n 个列表，时间复杂度为 O(n)。
   • 内层循环遍历每个列表中的 m 个元素，时间复杂度为 O(m)。
   • 整体时间复杂度为 O(n * m)，相比于暴力枚举所有组合（时间复杂度为 O(m^n)），该方法在列表数量较多和列表元素较多的情况下有显著优化。