如何求两个相关系数排序数组前i项含n个公共元素的最小i值

你有train和target两个数据表，行代表样本、列代表化学物质，表内数值为对应样本中化学物质的相对丰度，两个数据集的化学物质完全一致。你已经计算得到训练数据和目标数据之间斯皮尔曼相关系数的绝对值，需要找到最小的正整数i，使得两个相关系数排序数组的前i个元素中，共有n个相同的元素。

假设研究化学物质Y1，train和target数据集分别与Y1到Y10共10种化学物质的相关系数如下：

# train相关系数矩阵
     Y1  Y2  Y3  Y4  Y5  Y6  Y7  Y8  Y9  Y10
Y1:   1  -1 -.2  .5 -.9  .7  .1  .1 -.2  -.5

# target相关系数矩阵
     Y1  Y2  Y3  Y4  Y5  Y6  Y7  Y8  Y9  Y10
Y1:   1  .1  .2  -.7 .6  .4  .2  .5 -.5  -.2

对两组相关系数取绝对值后按降序排序，得到的排名顺序为：

# train排序结果
Y1:  Y1  Y2  Y5  Y6  Y4  Y10 Y9  Y3  Y7  Y8  

# target排序结果
Y1:  Y1  Y4  Y5  Y8  Y9  Y6  Y3  Y7  Y10 Y2

两组需要的5个公共元素为Y1、Y5、Y4、Y6、Y9，对应的最小i为7，即取两个数组的前7个元素即可集齐5个公共元素。

• 方案1：先分别对train和target中各化学物质的相关系数绝对值排名，再对两个排名列表取交集后取前N个元素。该方案不可行，两个数据集的化学物质完全一致，交集就是全部化学物质列表，排序规则仅由intersect()函数的第一个入参决定，无法得到符合要求的结果。
• 方案2：逐个增加i的取值，每次取train和target相关系数排名的前i个元素取交集，判断交集长度是否达到n，若未达到则i自增1后重复判断。该方案结果准确，但整体算法时间复杂度为O(n²)，效率较低，原使用的R代码如下：

common = c()
num = 10
i = num
while(length(common)<(num)){
    common = intersect(corr_train[2:(i+1)], corr_target[2:(i+1)])
    i = i + 1
}

算法思路 #

时间复杂度可优化到O(m log m)，m为总化学物质数量，思路如下：

1. 先为每个化学物质记录它在train排序列表中的位置、以及在target排序列表中的位置
2. 对每个物质，计算max(训练集排名, 目标集排名)：该值代表要让这个物质同时出现在两个列表的前i个元素中，i的最小取值
3. 将所有物质的该max值从小到大排序，第n个值就是你需要的最小i：前n个最小的max值对应的物质，就是最早能同时出现在两个列表前i位的n个公共元素，最大的那个max值就是满足条件的最小i

R实现代码 #

# 输入：corr_train是train排序后的化学物质向量，corr_target是target排序后的向量，n是需要的公共元素数量
find_min_i <- function(corr_train, corr_target, n) {
  # 生成每个物质的排名字典
  rank_train <- setNames(seq_along(corr_train), corr_train)
  rank_target <- setNames(seq_along(corr_target), corr_target)
  # 计算所有物质的max排名
  max_ranks <- pmax(rank_train[names(rank_target)], rank_target)
  # 取第n小的max值即为结果
  sort(max_ranks)[n]
}

# 示例调用，对应测试用例
corr_train <- c("Y1", "Y2", "Y5", "Y6", "Y4", "Y10", "Y9", "Y3", "Y7", "Y8")
corr_target <- c("Y1", "Y4", "Y5", "Y8", "Y9", "Y6", "Y3", "Y7", "Y10", "Y2")
find_min_i(corr_train, corr_target, 5) # 输出结果为7，符合示例预期

优势说明 #

该方案仅需要3次线性遍历（生成两个排名向量、计算max值）加一次排序，远低于原有方案的O(n²)，当化学物质数量很大时性能提升非常明显。

内容的提问来源于stack exchange，提问作者Daniel Cotter