时间戳

首页 > 解决方案 > 给定一个数组，每个元素计数多少分

java - 给定一个数组，每个元素计数多少分

问题描述

我有一个数字列表，现在我想从列表中取出一个数字并检查有多少元素可以将该数字除以余数为 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

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

标签： javaalgorithm

解决方案

  1. 从. Map_ O(N)_List
  2. 计算时间的每个元素的List除数O(sqrt(N))。使用频率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);
    }
}

推荐阅读