求优化通用函数：查找无序等差数列中的缺失数字

问题背景 #

需要实现一个高效的通用函数，用于从无序的等差数列中找出唯一缺失的数字。

现有实现示例 #

现有函数f可处理部分场景：

q)list1:12 3 6 15 18   / 缺失数字为9
q)f:{s:asc x; f:first s;e:last s; r where not (r:where 0b,e#((f - 1)#00b),1b) in x}
q)f list1
,9
q)list2:2 8 6 10   / 缺失数字为4
q)f list2
,4

拓展场景验证 #

对于以下同样缺失一个数字的等差数列，需验证通用函数的适用性：

q)list3:3 9 1 11 13 5 / 缺失数字为7

优化后的通用函数 #

原有实现通过生成大范围布尔数组查找缺失值，当数列首尾差距较大时效率偏低。以下优化函数通过计算等差数列公差直接生成完整数列，再定位缺失值，更高效且通用：

f_opt:{
    s:asc x;
    n:count s;
    full_n:n+1;  // 完整数列项数为当前项数+1（仅缺失一个数字）
    f:first s;
    e:last s;
    d:(e-f)%(full_n-1);  // 计算等差数列公差
    first f+d*til[full_n] where not f+d*til[full_n] in x
}

测试验证 #

q)f_opt list1
,9
q)f_opt list2
,4
q)f_opt list3
,7

函数说明 #

1. 先对输入列表排序，获取首项f和末项e；
2. 已知仅缺失一个数字，因此完整数列的项数为当前项数+1；
3. 利用等差数列公差公式d=(末项-首项)/(项数-1)计算公差；
4. 生成完整的等差数列，筛选出不在原列表中的唯一元素，即为缺失值。

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