大厂真题 / 京东

京东 2026-8-15 笔试真题 - 算法/数据方向

本场考试概述

考试时间：2026 年 8 月 15 日

考试岗位：算法/数据方向

难度评级：中等

考点分析：

第 1 题：Apriori、频繁项集、连接与剪枝（中等）
第 2 题：等量划分、折半枚举、按选取数量分桶、二分查找（中等偏难）

建议策略：

第 1 题的数据规模不大，但必须准确实现 Apriori 的逐层生成过程，尤其注意连接条件、子集剪枝和最终排序。
第 2 题先去掉题目中的决策背景，将目标化为“恰好选择一半元素，使两组和尽量接近”，再用折半枚举降低指数规模。
两题都要留意输出格式：第 1 题输出 JSON，第 2 题需要对每个询问单独输出一行。

第 1 题：抽检共现项集

题目描述

一次产线抽检记录中可能同时出现若干种零件，每种零件用一个整数编号表示，同一条记录内的编号互不相同。给定全部抽检记录以及最小支持计数 min_cnt，请按照 Apriori 算法找出所有频繁项集。

对项集 $X$，其支持计数定义为包含 $X$ 中全部编号的记录数：

\[\operatorname{sup}(X)=\left|\{R\mid R\in records,\ X\subseteq R\}\right|.\]

当且仅当 $\operatorname{sup}(X)\ge min_cnt$ 时，$X$ 是频繁项集。

算法按项集大小逐层进行：

统计每个单项的支持计数，得到频繁 $1$ 项集 $G_1$。
当 $k\ge2$ 时，由 $G_{k-1}$ 生成候选 $k$ 项集 $D_k$。所有项集均按编号升序保存。两个 $(k-1)$ 项集只有在前 $k-2$ 个元素相同、且前者末元素小于后者末元素时才能连接。
若候选的任意一个 $(k-1)$ 元子集不在 $G_{k-1}$ 中，则剪去该候选。
扫描记录，计算剩余候选的支持计数，保留支持计数不小于 min_cnt 的候选，得到 $G_k$。
当某一层频繁项集为空时终止，汇总此前得到的所有频繁项集。

输出时先按项集大小升序排列；大小相同时，按项集中的编号字典序升序排列。

输入描述

输入一行 JSON 对象，包含：

records：二维整数列表，表示抽检记录。记录条数为 $n$，满足 $1\le n\le24$；每条记录最多包含 $4$ 个互异编号。
min_cnt：正整数，满足 $min_cnt\ge1$。

输入格式示意：

{"records":[[1,2],[1,3]],"min_cnt":1}

输出描述

输出一行 JSON 数组。每个元素的格式为 [[id1,id2,...], support]，分别表示一个升序项集及其支持计数。

所有元素先按项集大小、再按字典序排列。若不存在频繁项集，输出空数组 []。

样例 1

输入

{"records":[[1,2],[1,2],[1,3],[2,3]],"min_cnt":2}

输出

[[[1],3],[[2],3],[[3],2],[[1,2],2]]

解释

编号 $1,2,3$ 的支持计数依次为 $3,3,2$，均为频繁单项。在三个二元候选中，只有 ${1,2}$ 出现了 $2$ 次；其余两个只出现 $1$ 次。频繁二项集只有一个，无法继续连接出三项候选。

样例 2

输入

{"records":[[2,3,5],[2,3,5],[2,3],[3,5]],"min_cnt":2}

输出

[[[2],3],[[3],4],[[5],3],[[2,3],3],[[2,5],2],[[3,5],3],[[2,3,5],2]]

思路分析

先将每条记录转为集合，以便使用集合包含关系判断候选是否出现在该记录中；项集本身使用升序元组保存，使连接、哈希查找和字典序排序都有唯一表示。

第一层：遍历所有记录，累计每个编号出现在多少条记录中，筛出支持计数达到阈值的单项集。

候选连接：设当前已有频繁 $(k-1)$ 项集。按字典序枚举其中的两项 left 和 right，若二者除末位外的前缀相同，就将两个不同的末元素合并，形成一个升序的 $k$ 项候选。由于枚举顺序已经保证 left < right，末元素也按递增顺序加入。

Apriori 剪枝：频繁项集的每个子集都必然频繁。因而对一个 $k$ 项候选，删除其中任意元素所得的所有 $(k-1)$ 元子集都必须位于上一层频繁集合中；只要有一个不在，就无需扫描记录计数。

支持计数：对通过剪枝的候选 $X$，遍历全部记录集合 $R$，累计满足 $X\subseteq R$ 的记录数。达到阈值的候选组成下一层频繁项集。

每条记录至多包含 $4$ 个编号，因此任何大小超过 $4$ 的项集支持计数都为 $0$，算法至多得到四层非空结果。最后统一按 (项集大小, 项集元组) 排序并序列化为 JSON。

正确性证明

引理 1：算法计算出的任意候选项集支持计数等于题目定义的支持计数。

证明：算法逐条考察记录 $R$，当且仅当候选 $X$ 的所有元素均属于 $R$，即 $X\subseteq R$ 时，将计数增加 $1$。因此最终计数恰好是包含 $X$ 的记录条数，也就是 $\operatorname{sup}(X)$。引理得证。

引理 2：剪枝过程不会删除任何频繁 $k$ 项集。

证明：若 $X$ 是频繁 $k$ 项集，则对它的任意 $(k-1)$ 元子集 $Y$，每条包含 $X$ 的记录必然也包含 $Y$，故 $\operatorname{sup}(Y)\ge\operatorname{sup}(X)\ge min_cnt$。所以 $Y$ 必在上一层频繁集合中。算法仅删除至少有一个子集不在上一层的候选，故不会删除频繁项集。引理得证。

引理 3：任意频繁 $k$ 项集都会被连接步骤生成。

证明：设频繁项集 $X=(x_1,x_2,\ldots,x_k)$ 已升序排列。由引理 2 的论证，它的两个子集 $(x_1,\ldots,x_{k-2},x_{k-1})$ 与 $(x_1,\ldots,x_{k-2},x_k)$ 均在 $G_{k-1}$ 中。两者前 $k-2$ 项相同，且 $x_{k-1}<x_k$，满足连接条件，连接结果正是 $X$。引理得证。

定理：算法输出且仅输出全部频繁项集，并给出正确支持计数和正确顺序。

证明：由引理 3 和引理 2，每一层的所有频繁项集都会进入计数阶段；由引理 1，它们会被正确保留，而不满足阈值的候选不会进入结果。因此逐层所得集合恰好是全部频繁项集。最终排序键先比较大小再比较升序元组，与题目顺序一致。定理得证。

ACM Python 代码

import json
import sys
from collections import Counter


def generate_candidates(previous):
    """由频繁 (k-1) 项集生成经过 Apriori 剪枝的 k 项候选。"""
    previous = sorted(previous)
    known = set(previous)
    candidates = set()

    for i in range(len(previous)):
        for j in range(i + 1, len(previous)):
            left, right = previous[i], previous[j]
            if left[:-1] != right[:-1]:
                continue

            candidate = left + (right[-1],)
            if all(
                candidate[:p] + candidate[p + 1:] in known
                for p in range(len(candidate))
            ):
                candidates.add(candidate)

    return sorted(candidates)


def solve():
    data = json.loads(sys.stdin.buffer.readline())
    records = [set(record) for record in data["records"]]
    min_cnt = int(data["min_cnt"])

    singleton_count = Counter()
    for record in records:
        singleton_count.update(record)

    support = {}
    level = []
    for value in sorted(singleton_count):
        count = singleton_count[value]
        if count >= min_cnt:
            itemset = (value,)
            level.append(itemset)
            support[itemset] = count

    all_frequent = []
    while level:
        all_frequent.extend(level)
        candidates = generate_candidates(level)
        next_level = []

        for candidate in candidates:
            candidate_set = set(candidate)
            count = sum(candidate_set <= record for record in records)
            if count >= min_cnt:
                next_level.append(candidate)
                support[candidate] = count

        level = next_level

    all_frequent.sort(key=lambda itemset: (len(itemset), itemset))
    answer = [[list(itemset), support[itemset]] for itemset in all_frequent]
    print(json.dumps(answer, separators=(",", ":")))


if __name__ == "__main__":
    solve()

复杂度分析

设不同编号总数为 $m$，第 $k$ 层通过剪枝后的候选集合为 $D_k$。每个候选要在 $n$ 条记录上做至多 $k$ 个元素的包含判断，因此计数部分的时间复杂度为

\[O\left(\sum_k |D_k|\cdot n\cdot k\right).\]

连接时还需两两检查上一层频繁项集，时间复杂度为 $O(\sum_k

G_{k-1}

^2\cdot k)$。由于单条记录最多有 $4$ 项，实际只需处理至多四层。保存记录、频繁项集与候选项集所需空间为 $O(nm+\sum_k(

G_k

D_k

)k)$；使用集合存记录时，记录本身实际只占 $O(4n)$ 个元素。

易错点

支持计数是“包含该项集的记录数”，同一编号不能因一条记录而重复贡献；将记录转成集合可以避免重复问题。
连接的是前 $k-2$ 项相同的两个 $(k-1)$ 项集，不能任意取并集。
只检查连接条件还不够，候选的每个 $(k-1)$ 元子集都必须频繁。
空输入结果应输出合法 JSON []；不要直接输出 Python 元组或字典。
最终顺序先比较项集大小，同大小时再按编号字典序比较。

第 2 题：双班次收益差

题目描述

有 $n$ 个工单需要平均分配给两个班次，其中 $n$ 为偶数，第 $i$ 个工单的收益为 $v_i$。每个班次必须恰好得到 $n/2$ 个工单。分配完成后，值班方会选择总收益较高的班次。

调度方希望让两个班次的收益尽量接近。请计算在最优分配下，两班总收益之差的最小值。

若其中一个班次所选工单的收益和为 $S$，全部工单收益和为

\[V=\sum_{i=1}^{n}v_i,\]

则另一个班次的收益为 $V-S$，两班差值为

\[\lvert S-(V-S)\rvert=\lvert2S-V\rvert.\]

输入描述

第一行输入整数 $q$，表示询问数量，满足 $1\le q\le80$。

每个询问包含两行：

第一行输入一个偶数 $n$，满足 $2\le n\le30$；
第二行输入 $n$ 个整数 $v_1,v_2,\ldots,v_n$，满足 $1\le v_i\le10^9$。

输出描述

对每个询问输出一行一个非负整数，表示两个班次总收益差的最小可能值。

样例

输入

输出

5
0

解释

第一个询问只能将两个工单分别放入两个班次，差值为 $

4-9

=5$。第二个询问可分为 ${3,8}$ 与 ${5,6}$，两边收益均为 $11$，最小差值为 $0$。

思路分析

选择一个班次的 $n/2$ 个工单后，另一个班次自动由剩余工单组成。因此问题等价于：在所有恰好选 $n/2$ 个元素的方案中，最小化 $\lvert2S-V\rvert$。

直接枚举所有等大子集最多需要考察 $\binom{30}{15}$ 种方案，询问较多时无法接受。将数组拆成左右两半，每半至多 $15$ 个元素，分别枚举全部子集即可把指数规模降到 $2^{15}$。

枚举子集时不能只记录子集和，还要按照选取元素个数分桶：

$L_c$：左半部分恰好选择 $c$ 个元素所能得到的所有子集和；
$R_d$：右半部分恰好选择 $d$ 个元素所能得到的所有子集和。

若左边选择 $c$ 个，右边必须选择 $d=n/2-c$ 个。答案为

\[\min_{c+d=n/2}\ \min_{s\in L_c,\ t\in R_d}\lvert2(s+t)-V\rvert.\]

对每个有效的 $d$，将 $R_d$ 中的和乘以 $2$ 后排序。固定左侧子集和 $s$，目标变成寻找最接近 $V-2s$ 的 $2t$。在有序数组中二分得到插入位置，只需检查该位置及其前一个位置。

全程使用整数表达式，不需要计算 $(V-2s)/2$，从而避免除法取整造成的边界问题。Python 整数可直接容纳最大约 $3\times10^{10}$ 的总收益。

正确性证明

引理 1：算法枚举了每个半区的全部子集，且将每个子集和放入了与其元素个数对应的桶中。

证明：枚举掩码 mask 时，掩码的每一位唯一决定对应元素是否被选择，所以半区的每个子集与一个掩码一一对应。算法计算该掩码的元素个数和元素和，并分别放入该个数的桶，因此没有遗漏或放错。引理得证。

引理 2：对任意恰好包含 $n/2$ 个工单的选择，算法都会考察其左右两半子集和的组合。

证明：任意选择都能唯一拆成左半子集与右半子集。若左半选了 $c$ 个，则右半必选 $d=n/2-c$ 个。由引理 1，两者的和分别位于 $L_c$ 与 $R_d$，算法会处理这一对互补桶。固定左侧和 $s$ 时，算法在 $R_d$ 中寻找使目标最小的右侧和。故该选择对应的差值不会被遗漏。引理得证。

引理 3：固定 $s$ 后，二分检查的两个位置中必有使 $

2t-(V-2s)

$ 最小的右侧子集和。

证明：设目标值为 $T=V-2s$。在排好序的 $2R_d$ 中，二分位置是第一个不小于 $T$ 的元素。该位置之后的元素都不小于它，不会更接近 $T$；该位置之前除紧邻元素外都不大于紧邻元素，也不会更接近 $T$。因此最近值只可能是插入位置或其前一个位置。引理得证。

定理：算法输出每个询问中两班收益差的最小值。

证明：由引理 2，所有满足人数限制的划分都被纳入搜索；由引理 3，算法对每个左侧子集都取得了对应右侧桶中的最优搭配。算法再对全部合法选取数量和左侧子集取最小值，因此所得结果正是所有等量划分中 $\lvert2S-V\rvert$ 的最小值。定理得证。

ACM Python 代码

import sys
from bisect import bisect_left


def subset_sums_by_count(values):
    """枚举全部子集，并按子集大小保存子集和。"""
    size = len(values)
    limit = 1 << size
    sums = [0] * limit
    buckets = [[] for _ in range(size + 1)]
    buckets[0].append(0)

    for mask in range(1, limit):
        lowbit = mask & -mask
        index = lowbit.bit_length() - 1
        previous = mask ^ lowbit
        sums[mask] = sums[previous] + values[index]
        buckets[mask.bit_count()].append(sums[mask])

    return buckets


def minimum_gap(values):
    n = len(values)
    middle = n // 2
    need_count = n // 2
    total = sum(values)

    left = subset_sums_by_count(values[:middle])
    right = subset_sums_by_count(values[middle:])
    doubled_right = [sorted(2 * value for value in bucket) for bucket in right]

    best = total
    for left_count, left_sums in enumerate(left):
        right_count = need_count - left_count
        if not 0 <= right_count < len(doubled_right):
            continue

        candidates = doubled_right[right_count]
        for left_sum in left_sums:
            target = total - 2 * left_sum
            position = bisect_left(candidates, target)

            if position < len(candidates):
                best = min(best, candidates[position] - target)
            if position > 0:
                best = min(best, target - candidates[position - 1])

            if best == 0:
                return 0

    return best


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    iterator = iter(data)
    query_count = next(iterator)
    answers = []

    for _ in range(query_count):
        n = next(iterator)
        values = [next(iterator) for _ in range(n)]
        answers.append(str(minimum_gap(values)))

    sys.stdout.write("\n".join(answers))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：对单个询问，两半长度分别记为 $a$ 和 $b$，其中 $a,b\le15$。枚举子集需要 $O(2^a+2^b)$ 时间；分桶排序的总时间不超过 $O(2^b\log 2^b)$；每个左侧子集进行一次二分，时间为 $O(2^a\log 2^b)$，整体可概括为 $O(n2^{n/2})$。

空间复杂度：保存两侧全部子集和需要 $O(2^{n/2})$ 空间。各询问依次处理，空间不会乘以 $q$。

易错点

两组不仅要覆盖全部工单，还必须各有恰好 $n/2$ 个，因此子集和必须按选取数量分桶。
优化目标是 $\lvert2S-V\rvert$，不是只找最接近 $V/2$ 的任意大小子集。
二分后要同时检查插入位置和它的前一个位置，并处理数组两端的边界。
最大总收益可达 $3\times10^{10}$；在固定宽度语言中必须使用 64 位整数。
多组询问应逐组独立计算，上一组的子集桶不能复用。

小结

Apriori 的核心是支持计数的反单调性：频繁项集的所有子集都频繁，据此可以在计数前大量剪枝。
等量划分可以写成最小化 $\lvert2S-V\rvert$，折半后按选择数量配对左右子集，再用二分寻找最接近目标的和。
第一题重在严格复现规则，第二题重在识别指数枚举并利用 $n\le30$ 的折半边界。

这篇文章有帮助吗？

| GitHub 留言