Как создать список, соответствующий каждому числу от 2 до 100, который будет содержать числа из массива, кратные ему?

Question

Недавно я столкнулся с этим вопросом и не мог найти оптимальное решение для него.

Предположим, у нас есть массив чисел любого диапазона, например, 9, -3,0,4,11,2, -8, ..... Нам нужно вывести числа от 2 до 100, и в соответствии с каждым из них нам нужно вывести список чисел из массива так, чтобы число в массиве делилось на него. Пример: Используя существующий массив в примере, 2 -> 4,2,-8,... 3 -> -3,9,... 4 -> 4,-8,... и так до 100.

Я попытался выработать решение, разделив каждое число массива на числа от 2 до 100 и затем создав список, соответствующий каждому из них. Но это не показалось мне оптимальным решением.

Я даже пытался сгруппировать числа, например, число, которое делится на 8, будет делиться на 2 и 4, поэтому нам не нужно делить их снова. Это уменьшило бы некоторые операции и сложность, но, в свою очередь, потребовало бы создания таких групп.

Пожалуйста, кто-нибудь может помочь найти оптимальное решение этой проблемы, уменьшив необходимость деления каждого числа на 2 до 100.

Answer 1

Для решения данной проблемы я бы выбрал один из двух следующих подходов:

Версия 1

Два простых вложенных цикла в сочетании с методом map.computeIfAbsent

int[] myArray = {3,5,1,-7,6,34,88,2,-8,9,10,4,33};
Map<Integer,List<Integer>> version1 = new HashMap<>();
for(int i = 2; i< 100; i++){
    for(int x : myArray){
        if(x%i==0)
           version1.computeIfAbsent(i, k -> new ArrayList<>()).add(x);
    }            
}
System.out.println(version1);

Версия 2

Решение только с потоковыми операциями

    Map<Integer,List<Integer>> version2 = Arrays.stream(myArray).distinct().boxed()
            .flatMap(p -> IntStream.range(2, 100).filter(i -> p%i ==0).boxed()
                    .map(l->new AbstractMap.SimpleEntry<>(l,p)))
            .collect(Collectors.groupingBy(Map.Entry::getKey,
                    Collectors.mapping(Map.Entry::getValue, Collectors.toList())));

    System.out.println(version2);

Конечно, существуют более элегантные решения или решения, которые являются оптимальными с точки зрения сложности. Но я думаю, что подходы здесь короткие и легко читаемые.

Answer 2

Если вы сохраняете каждый подсписок как есть, вы можете использовать предыдущие результаты для ограничения длины списка:

    List<List<Integer>> lists = new ArrayList<>();
    lists.add(list); // at 0: never used
    lists.add(list);
    for (int i = 2; i <= 100; ++i) {
        for (int j = i/2; j > 0; --j) {
            if (i%j == 0) {
                lists.add(extractMultiples(lists.get(j), i));
                break;
            }
        }
    }
    for (int i = 2; i <= 100; ++i) {
        System.out.println(i + ": " + lists.get(i));
    }

с методом extractMultiples:

public static List<Integer> extractMultiples(List<Integer> list, int n) {
    List<Integer> result = new ArrayList<>();
    for (int x: list) {
        if (x%n == 0) {
            result.add(x);
        }
    }
    return result;
}