如何统计数组中可被至少一个其他元素整除的元素数量？求最优解

阿华AIGC实验室

2026-5-25

如何高效找出数组中能被至少一个其他元素整除的元素数量？

嘿，这个问题我之前也碰到过，暴力法嵌套循环（挨个检查每个元素是否能被其他元素整除）的O(n²)时间复杂度，在数组规模变大的时候简直没法用。咱们来聊聊更优的解法，时间复杂度能做到O(M log M)，其中M是数组中的最大值，比暴力法高效太多！

核心思路

统计元素频率：先搞清楚数组里每个数字出现了多少次，用一个频率数组（或者哈希表）来存，这样能快速判断某个数字是否存在于数组中。
遍历倍数标记符合条件的元素：找到数组中的最大值max_num，因为任何数的倍数都不会超过这个最大值。然后从1到max_num遍历每个数字x：
- 如果x在数组中存在，就遍历它的所有倍数（2x、3x...直到超过max_num），只要某个倍数y在数组中存在，就标记y为「符合条件」（因为y能被x整除，且x≠y，满足“被至少一个其他元素整除”）。
- 如果x在数组中出现多次（比如[2,2]），那x自己也符合条件，因为有其他相同的元素可以整除它。
统计结果：最后遍历原数组，数一下所有被标记为符合条件的元素总数。

示例演示（以数组[1,2,3,4]为例）

频率数组：freq[1]=1、freq[2]=1、freq[3]=1、freq[4]=1，最大值max_num=4。
遍历x=1：它的倍数是2、3、4，这些都在数组里，所以标记2、3、4为符合条件。
遍历x=2：倍数是4，已经被标记过，无需重复操作。
遍历x=3：倍数是6，超过最大值，直接跳过。
遍历x=4：倍数是8，超过最大值，直接跳过。
最终符合条件的元素是2、3、4，总数为3，和示例结果一致。

代码实现（Python）

def count_divisible_elements(arr):
    if not arr:
        return 0
    
    # 单独处理数组中的0元素
    zero_count = arr.count(0)
    non_zero_arr = [num for num in arr if num != 0]
    
    # 全是0的情况：每个0都能被其他0整除
    if not non_zero_arr:
        return len(arr)
    
    max_num = max(non_zero_arr)
    # 初始化频率数组
    freq = [0] * (max_num + 1)
    for num in non_zero_arr:
        freq[num] += 1
    
    # 标记符合条件的非0元素
    is_divisible = [False] * (max_num + 1)
    for x in range(1, max_num + 1):
        if freq[x] == 0:
            continue
        # 遍历x的所有倍数
        multiple = 2 * x
        while multiple <= max_num:
            if freq[multiple] > 0:
                is_divisible[multiple] = True
            multiple += x
        # 同一元素出现多次的情况
        if freq[x] > 1:
            is_divisible[x] = True
    
    # 统计非0元素中符合条件的数量
    non_zero_count = 0
    for num in non_zero_arr:
        if is_divisible[num]:
            non_zero_count += 1
    
    # 所有0都符合条件（因为存在非0元素可以整除它）
    return non_zero_count + zero_count

# 测试用例
print(count_divisible_elements([1,2,3,4]))    # 输出3
print(count_divisible_elements([2,2,4]))       # 输出3
print(count_divisible_elements([0,1,2]))       # 输出1
print(count_divisible_elements([0,0,0]))        # 输出3