LeetCode 补充题 116. 内存受限的大文件字符串交集

2026-09-13 HGNULB 约 16 分钟

文章信息 3 个分类 2 个标签

分类

补充题困难贝壳

题目描述

给你两个文本文件 A 和 B，文件中的每一行都是一条 UTF-8 字符串。两个文件不能同时放入内存。

请找出在两个文件中都出现过的字符串，每个不同的值只输出一次，输出顺序不限。字符串按字节比较，并且区分大小写。

允许使用临时磁盘空间，但单条记录必须能够放入给定的内存预算。

示例 1：

输入： 文件 A 的各行为 ["apple","pear","apple"]，文件 B 的各行为 ["pear","plum","apple"]。
输出： ["apple","pear"]
解释： 示例用列表表示文件中的各行。apple 和 pear 都出现在两个文件中；重复的 apple 只输出一次，输出顺序不限。

提示：

每行是一条合法的 UTF-8 字符串，使用 LF 或 CRLF 分行，行内不包含回车或换行。
两个文件不能同时放入内存，允许使用临时磁盘空间。
字符串按字节比较，并且区分大小写。
单条记录的长度必须适合给定的内存预算。

题意分析

把一整个文件装进 HashSet 可能超过内存限制。哈希分桶也不能保证每个桶足够小，重复热点和碰撞都可能造成偏斜。外部排序将大文件拆成能放进内存的有序段，再分批归并，最后用双指针求交集。

解法：外部排序后归并

核心思路

[!blue]

先把每个文件拆成内存可容纳的数据块，块内排序去重后写成有序段。随后每轮两两归并：取较小记录写出，相等时只写一次并同时推进两侧。输入段已经各自去重，所以合并结果仍有序且无重复；奇数个段中的最后一段直接移到下一轮。

两个文件各自成为一条有序唯一记录流后，再做求交。若 x < y，另一条流后续记录都不小于 y，所以 x 不可能再匹配，可以安全前进；对称处理 y < x。相等时输出一次并同时前进，一侧耗尽即结束。

内存只保存当前排序块或少量流缓冲区，结果边比较边写出。runLimit 是记录数限制，不是字节限制：必须结合单条记录长度上界及对象、缓冲区开销选取，不能因设置了行数就宣称满足任意内存预算。文件名按轮次与编号生成，避免把全部段路径装入内存。

解题步骤

按可用内存拆出数据块，在内存中排序去重，写为临时有序段。

用有限路归并逐步合并有序段。路数受可用内存与文件句柄上限约束，超出时分多轮。

对最终两条有序流做归并求交集，结果流式写出。

无论成功还是失败，都清理本次创建的临时目录，保留两个输入文件。

代码实现

runLimit 限制每个内存排序段的最大记录数，每条记录长度上限为 L 时，内存为 $O(runLimit\cdot L)$，另有固定读写缓冲区。归并固定为二路，段文件通过轮次和编号定位，不在内存保存全部文件名。输入使用 LF 或 CRLF 分行，行内不含回车与换行，字符串为合法 UTF-8。Java 按 UTF-8 无符号字节比较，Go 的字符串比较天然按字节进行。输出写入调用方提供的独立 Writer；调用方负责最终关闭输出。

class Solution {
    private int compare(String a, String b) {
        return Arrays.compareUnsigned(
                a.getBytes(java.nio.charset.StandardCharsets.UTF_8),
                b.getBytes(java.nio.charset.StandardCharsets.UTF_8));
    }

    private Path run(Path work, String prefix, int pass, long index) {
        return work.resolve(prefix + "-" + pass + "-" + index);
    }

    private BufferedReader reader(Path path) throws IOException {
        return Files.newBufferedReader(path, java.nio.charset.StandardCharsets.UTF_8);
    }

    private BufferedWriter writer(Path path) throws IOException {
        return Files.newBufferedWriter(path, java.nio.charset.StandardCharsets.UTF_8);
    }

    private void merge(Path first, Path second, Path output) throws IOException {
        try (BufferedReader a = reader(first);
                BufferedReader b = reader(second);
                BufferedWriter out = writer(output)) {
            String x = a.readLine();
            String y = b.readLine();

            while (x != null || y != null) {
                if (y == null || x != null && compare(x, y) < 0) {
                    out.write(x);
                    out.newLine();
                    x = a.readLine();
                } else if (x == null || compare(x, y) > 0) {
                    out.write(y);
                    out.newLine();
                    y = b.readLine();
                } else {
                    out.write(x);
                    out.newLine();
                    x = a.readLine();
                    y = b.readLine();
                }
            }
        }
    }

    private Path sorted(Path input, Path work, String prefix, int runLimit) throws IOException {
        long count = 0;

        try (BufferedReader in = reader(input)) {
            while (true) {
                List<String> block = new ArrayList<>();
                String line;

                while (block.size() < runLimit && (line = in.readLine()) != null) {
                    block.add(line);
                }

                if (block.isEmpty()) {
                    break;
                }

                block.sort(this::compare);

                try (BufferedWriter out = writer(run(work, prefix, 0, count++))) {
                    String previous = null;

                    for (String value : block) {
                        if (!value.equals(previous)) {
                            out.write(value);
                            out.newLine();
                        }

                        previous = value;
                    }
                }
            }
        }

        int pass = 0;

        if (count == 0) {
            Path empty = run(work, prefix, 0, 0);

            Files.createFile(empty);

            return empty;
        }

        while (count > 1) {
            long nextCount = 0;

            for (long i = 0; i < count; i += 2) {
                Path first = run(work, prefix, pass, i);
                Path output = run(work, prefix, pass + 1, nextCount++);

                if (i + 1 == count) {
                    Files.move(first, output);
                } else {
                    Path second = run(work, prefix, pass, i + 1);

                    merge(first, second, output);
                    Files.delete(first);
                    Files.delete(second);
                }
            }

            count = nextCount;
            pass++;
        }

        return run(work, prefix, pass, 0);
    }

    public void intersect(Path first, Path second, Writer output, int runLimit) throws IOException {
        if (runLimit <= 0) {
            throw new IllegalArgumentException("runLimit must be positive");
        }

        Path work = Files.createTempDirectory("intersection-");

        try {
            Path left = sorted(first, work, "a", runLimit);
            Path right = sorted(second, work, "b", runLimit);

            try (BufferedReader a = reader(left);
                    BufferedReader b = reader(right)) {
                String x = a.readLine();
                String y = b.readLine();

                while (x != null && y != null) {
                    int comparison = compare(x, y);

                    if (comparison == 0) {
                        output.write(x);
                        output.write('\n');
                        x = a.readLine();
                        y = b.readLine();
                    } else if (comparison < 0) {
                        x = a.readLine();
                    } else {
                        y = b.readLine();
                    }
                }
            }

            output.flush();
        } finally {
            try (DirectoryStream<Path> files = Files.newDirectoryStream(work)) {
                for (Path file : files) {
                    Files.deleteIfExists(file);
                }
            }

            Files.deleteIfExists(work);
        }
    }
}

import (
    "bufio"
    "errors"
    "fmt"
    "io"
    "os"
    "path/filepath"
    "sort"
    "strings"
)

func readLine(in *bufio.Reader) (string, bool, error) {
    line, err := in.ReadString('\n')
    if err != nil && err != io.EOF {
        return "", false, err
    }
    if len(line) == 0 && err == io.EOF {
        return "", false, nil
    }
    return strings.TrimSuffix(strings.TrimSuffix(line, "\n"), "\r"), true, nil
}

func runPath(work, prefix string, pass, index int) string {
    return filepath.Join(work, fmt.Sprintf("%s-%d-%d", prefix, pass, index))
}

func mergeRuns(first, second, output string) (err error) {
    a, err := os.Open(first)
    if err != nil {
        return err
    }
    defer a.Close()
    b, err := os.Open(second)
    if err != nil {
        return err
    }
    defer b.Close()
    out, err := os.Create(output)
    if err != nil {
        return err
    }
    defer func() {
        err = errors.Join(err, out.Close())
    }()
    ra, rb, w := bufio.NewReader(a), bufio.NewReader(b), bufio.NewWriter(out)
    x, hasX, err := readLine(ra)
    if err != nil {
        return err
    }
    y, hasY, err := readLine(rb)
    if err != nil {
        return err
    }
    for hasX || hasY {
        takeX := hasX && (!hasY || x <= y)
        takeY := hasY && (!hasX || y <= x)
        value := y
        if takeX {
            value = x
        }
        if _, err = w.WriteString(value + "\n"); err != nil {
            return err
        }
        if takeX {
            x, hasX, err = readLine(ra)
            if err != nil {
                return err
            }
        }
        if takeY {
            y, hasY, err = readLine(rb)
            if err != nil {
                return err
            }
        }
    }
    return w.Flush()
}

func writeRun(path string, block []string) (err error) {
    out, err := os.Create(path)
    if err != nil {
        return err
    }
    defer func() {
        err = errors.Join(err, out.Close())
    }()
    w := bufio.NewWriter(out)
    for i, value := range block {
        if i == 0 || value != block[i-1] {
            if _, err = w.WriteString(value + "\n"); err != nil {
                return err
            }
        }
    }
    return w.Flush()
}

func sortedFile(input, work, prefix string, runLimit int) (string, error) {
    in, err := os.Open(input)
    if err != nil {
        return "", err
    }
    defer in.Close()
    reader := bufio.NewReader(in)
    count := 0
    for {
        block := make([]string, 0, runLimit)
        for len(block) < runLimit {
            line, ok, err := readLine(reader)
            if err != nil {
                return "", err
            }
            if !ok {
                break
            }
            block = append(block, line)
        }
        if len(block) == 0 {
            break
        }
        sort.Strings(block)
        if err := writeRun(runPath(work, prefix, 0, count), block); err != nil {
            return "", err
        }
        count++
    }
    if count == 0 {
        path := runPath(work, prefix, 0, 0)
        return path, writeRun(path, nil)
    }
    pass := 0
    for count > 1 {
        nextCount := 0
        for i := 0; i < count; i += 2 {
            first := runPath(work, prefix, pass, i)
            output := runPath(work, prefix, pass+1, nextCount)
            nextCount++
            if i+1 == count {
                if err := os.Rename(first, output); err != nil {
                    return "", err
                }
            } else {
                second := runPath(work, prefix, pass, i+1)
                if err := mergeRuns(first, second, output); err != nil {
                    return "", err
                }
                if err := os.Remove(first); err != nil {
                    return "", err
                }
                if err := os.Remove(second); err != nil {
                    return "", err
                }
            }
        }
        count = nextCount
        pass++
    }
    return runPath(work, prefix, pass, 0), nil
}

func intersect(first, second string, output io.Writer, runLimit int) (err error) {
    if runLimit <= 0 {
        return fmt.Errorf("runLimit must be positive")
    }
    work, err := os.MkdirTemp("", "intersection-")
    if err != nil {
        return err
    }
    defer func() {
        err = errors.Join(err, os.RemoveAll(work))
    }()
    left, err := sortedFile(first, work, "a", runLimit)
    if err != nil {
        return err
    }
    right, err := sortedFile(second, work, "b", runLimit)
    if err != nil {
        return err
    }
    a, err := os.Open(left)
    if err != nil {
        return err
    }
    defer a.Close()
    b, err := os.Open(right)
    if err != nil {
        return err
    }
    defer b.Close()
    ra, rb := bufio.NewReader(a), bufio.NewReader(b)
    x, hasX, err := readLine(ra)
    if err != nil {
        return err
    }
    y, hasY, err := readLine(rb)
    if err != nil {
        return err
    }
    for hasX && hasY {
        takeX, takeY := x <= y, y <= x
        if x == y {
            if _, err = io.WriteString(output, x+"\n"); err != nil {
                return err
            }
        }
        if takeX {
            x, hasX, err = readLine(ra)
            if err != nil {
                return err
            }
        }
        if takeY {
            y, hasY, err = readLine(rb)
            if err != nil {
                return err
            }
        }
    }
    return nil
}

系统工具写法：

下面复用系统的外部排序和有序集合求交工具。保存为脚本后，以两个输入路径作为参数执行。sort -S 控制排序缓冲区，进程总内存还包含其他开销；应根据实际内存预算调小该值。TMPDIR 可指定有足够空间的临时磁盘。按题目不含行内回车的约定，先用 tr 去掉 CR，再单独执行排序；这样统一 LF/CRLF，并让读取或规范化失败直接退出，不被后续管道命令掩盖。

#!/bin/sh
set -eu
if [ "$#" -ne 2 ]; then
    echo "usage: $0 file-a file-b" >&2
    exit 2
fi
work=$(mktemp -d)
trap 'rm -rf "$work"' EXIT HUP INT TERM
export LC_ALL=C
tr -d '\r' < "$1" > "$work/a-normalized"
sort -S 64M -T "$work" -u -- "$work/a-normalized" > "$work/a"
tr -d '\r' < "$2" > "$work/b-normalized"
sort -S 64M -T "$work" -u -- "$work/b-normalized" > "$work/b"
comm -12 "$work/a" "$work/b"

复杂度分析

时间复杂度：比较次数为 $O(N \log N + M \log M)$，归并求交 $O(N+M)$，字符串比较还需计入字符长度。

空间复杂度：内存受排序缓冲区、归并路数和最大单条记录长度影响；临时磁盘空间与输入量同阶。若一条记录本身就超过内存预算，需要另定分段比较方案。

关键点总结

[!green]

外部排序把内存限制转化为多轮磁盘归并。两边必须采用相同的排序规则，才能用有序流求交；LC_ALL=C 统一按字节排序。

易错点总结

[!yellow]

两边必须分别排序去重，再做有序流求交，不能把一个文件内部的重复当成交集。LF 与 CRLF 需要统一，否则同一条记录会因末尾回车不同而失配。临时文件只放在本次创建的目录中；Java/Go 输出写入独立 Writer，系统工具版输出到标准输出，输入文件保持只读。

相似题目

题目	难度	关联与区别
23. 合并 K 个升序链表	困难	有序段可视为多条有序流，外部归并还需限制同时打开的路数与缓冲区。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/85490436

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！