Senior

Il y a deux fichiers, chacun contenant des valeurs entières ligne par ligne. Quels algorithmes peuvent être utilisés pour trouver l'intersection de ces deux ensembles?

sobes.tech IA

Réponse de l'IA

Для поиска пересечения двух множеств целочисленных значений из файлов можно использовать несколько подходов:

Считывание в множества (Set)
- Считать все значения из первого файла в HashSet.
- Считать значения из второго файла по одному и проверять наличие в первом множестве.
- Все совпадающие элементы — пересечение.
Сортировка и двухуказательный метод
- Считать оба файла в массивы.
- Отсортировать оба массива.
- Использовать два указателя для одновременного прохода по массивам и поиска общих элементов.
Использование потоков и фильтрации (Java 8+)
- Считать файлы как Stream<Integer>.
- Преобразовать один поток в Set для быстрого поиска.
- Отфильтровать второй поток по наличию в этом Set.

Пример с использованием HashSet:

import java.nio.file.*;
import java.io.IOException;
import java.util.*;

public class IntersectionFinder {
    public static Set<Integer> findIntersection(Path file1, Path file2) throws IOException {
        Set<Integer> set1 = new HashSet<>();
        try (Stream<String> lines = Files.lines(file1)) {
            lines.map(Integer::parseInt).forEach(set1::add);
        }

        Set<Integer> intersection = new HashSet<>();
        try (Stream<String> lines = Files.lines(file2)) {
            lines.map(Integer::parseInt)
                 .filter(set1::contains)
                 .forEach(intersection::add);
        }

        return intersection;
    }
}

Этот метод эффективен при большом объёме данных, так как операции с HashSet имеют амортизированную сложность O(1).

Précédent Suivant