京东9月19日机考笔试 风控AUC排序题解

《面试题目》

1. 编程题（风控排序评估）：给定 m 笔交易的真实标签 t_i（0 正常、1 欺诈）和模型风险分 s_i（越大越像欺诈），按 Mann-Whitney U 的秩统计计算 AUC，分数相同的交易必须取平均名次，输出保留 6 位小数。样例输入 m=5、标签 0 1 1 0 1、分数 1.0 2.0 2.0 3.0 4.0，输出 0.666667。

《参考解析》

平均名次怎么算：把交易按风险分从小到大排序，名次从 1 起。若连续若干笔分数相同、占住第 L 到第 R 个位置，则这几笔都记 (L+R)/2。实现上排序后单次扫描，遇到同分就把区间一次扩满，再把区间内所有元素写同一个平均名次。样例里两个 2.0 占第 2、3 位，各记 2.5。最常见的错是按出现顺序硬拆成 1、2、3，这等于人为规定并列样本有先后，平行样本被算成「一对一错」，AUC 会偏。

从正类名次和还原 AUC：记欺诈笔数 k、正常笔数 g、欺诈样本名次和 S。如果所有欺诈都排在最前面，名次和最小是 1+2+…+k = k(k+1)/2；多出来的 V = S − k(k+1)/2 就是正类「赢过」负类的对数，其中并列各计 0.5。正负样本一共 k·g 对，所以 AUC = V/(k·g)。这也正是 AUC 的概率解释：随机取一正一负，正类分数更高的概率。

四类常见假解：一是并列按顺序硬拆名次；二是名次从 0 起算，导致减去的最小名次和错位；三是按分数从大到小排序却仍套同一个公式（等价于算 1−AUC）；四是只统计严格大于、并列不计 0.5。另外要顺手处理除零：k 或 g 为 0 时（全正或全负）直接返回 0，不要让浮点异常把样例之外的测试点带崩。同分比较用读入后的 double 直接 == 即可（相同字面量解析结果一致），但别用 1e-9 之类的近似阈值，那会把本来不相等的分数并到一起。

复杂度与实现：排序是唯一的大头，时间 O(m log m)、空间 O(m)，m 到 1e6 也稳。参考实现：

def auc(labels, scores):
    m = len(labels)
    order = sorted(range(m), key=lambda i: scores[i])
    rank = [0.0] * m
    i = 0
    while i < m:                      # 把同分区间一次扩满
        j = i
        while j + 1 < m and scores[order[j + 1]] == scores[order[i]]:
            j += 1
        avg = (i + 1 + j + 1) / 2.0   # 名次从 1 起，区间 [i+1, j+1]
        for t in range(i, j + 1):
            rank[order[t]] = avg
        i = j + 1
    k = sum(labels)
    if k == 0 or k == m:
        return 0.0
    s = sum(rank[i] for i in range(m) if labels[i] == 1)
    v = s - k * (k + 1) / 2.0
    return v / (k * (m - k))

输出用 %.6f（C/C++ 的 setprecision(6)），注意别用默认精度把 0.666667 打成 0.66667。