给定每个元素计数的数组有多少可除性

Question

我有一个数字列表，现在我想从列表中取一个数字，并检查有多少个元素可以将这个数字与余数除以0。

这是我的代码：

public static void countDivibilies(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        int e = list.get(i);
        int count = 0;
        for (int j = 0; j < list.size(); j++) {
            int k = list.get(j);
            if (e % k == 0) {
                count++;
            }
        }
        System.out.println(e + " : " + count);
    }
}

对于示例输入：

2, 4, 8, 2

输出是:

2 : 2
4 : 3
8 : 4
2 : 2

但是此代码以 O（n2） 的时间复杂度运行。但是我的输入列表大小范围最大为 10 5，每个元素也在 1 到 10⁵ 之间。那么如何提高这个程序的时间复杂度呢？

Answer 1

1. 从List在O（N）时间内创建频率Map。
2. 在O（sqrt（N））时间内计算List每个元素的除数。使用频率Map查找元素在List中有多少个除数。总时间复杂度为O（Nsqrt（N））。

public static void countDivibilies(List<Integer> list) {
    Map<Integer, Integer> freq = list.stream()
       .collect(Collectors.toMap(x -> x, x -> 1, Integer::sum));
    for(int x : list){
        int count = 0;
        for(int i = 1; i * i <= x; i++){
            if(x % i == 0) {
                count += freq.getOrDefault(i, 0);
                if(x / i != i) //don't overcount square root
                   count += freq.getOrDefault(x / i, 0);
            }
        }
        System.out.println(x + " : " + count);
    }
}