优化R语言查找等差数列缺失项函数：解决超时问题

我来帮你解决这个超时的问题——核心问题出在你找公差的方式太笨重了，咱们换个更聪明的思路！

问题回顾 #

你正在编写findMissing(list)函数，用于找出等差数列中缺失的非首尾项。当前的find_missing小测试用例没问题，但跑102个测试用例时超时（超12秒）。原代码靠sort(table(diff(sequence)))算公差，排序开销太大；你试了几种替代方法，但效率反而更低，现在需要高效的实现方案。

你的原代码：

find_missing <- function(sequence){
 len <- length(sequence)
 if(len > 3){
 my_diff <- as.integer(names(sort(table(diff(sequence)), decreasing = TRUE))[1])
 complete_seq <- seq(sequence[1], sequence[len], my_diff)
 }else{
 differences <- diff(sequence)
 complete_seq_1 <- seq(sequence[1],sequence[len],differences[1])
 complete_seq_2 <- seq(sequence[1],sequence[len],differences[2])
 if(length(complete_seq_1) == 4){
 complete_seq <- complete_seq_1
 }else{
 complete_seq <- complete_seq_2
 }
 }
 complete_seq[!complete_seq %in% sequence]
}

测试示例：

find_missing(c(1,3,5,9,11)) # 预期返回7
find_missing(c(1,5,7)) # 预期返回3

你尝试过的替代方法：

• 用pracma包的Mode函数：

  library(pracma)
  Mode(diff(sequence))
  

• 用dplyr分组统计：

  library(dplyr)
  (data.frame(diff_1 = diff(sequence)) %>% group_by(diff_1) %>% summarise(count = n()) %>% ungroup() %>% filter(count==max(count)))[1]
  

• 自定义MaxTable函数：

  MaxTable <- function(sequence, mult = FALSE) {
   differences <- diff(sequence)
   if (!is.factor(differences)) differences <- factor(differences)
   A <- tabulate(differences)
   if (isTRUE(mult)) {
   as.integer(levels(differences)[A == max(A)])
   } else as.integer(levels(differences)[which.max(A)])
   }
  

高效解决方案 #

其实等差数列的公差有个更直接的计算逻辑，完全不用统计差值频率：

对于仅缺失一个非首尾项的等差数列，总差值（尾项 - 首项）除以原序列的长度，就是真实的公差。因为完整序列的长度是原长度+1，公差公式是(last - first)/(complete_len - 1)，代入complete_len = len + 1，就得到(last - first)/len。

基于这个思路，我们可以写出极简且高效的代码：

find_missing <- function(sequence) {
  len <- length(sequence)
  # 直接计算真实公差，跳过所有频率统计/排序操作
  true_diff <- (sequence[len] - sequence[1]) / len
  # 生成完整的等差数列
  complete_seq <- seq(sequence[1], sequence[len], true_diff)
  # 返回唯一缺失的非首尾项
  complete_seq[!complete_seq %in% sequence]
}

为什么这个方法快？

• 彻底抛弃了table、sort、分组统计这些O(n log n)复杂度的操作，所有步骤都是线性时间O(n)
• 不需要依赖任何第三方包，减少了额外的加载和调用开销
• 逻辑简洁，不管序列长短，都能快速处理

测试验证

find_missing(c(1,3,5,9,11)) # 输出7，正确
find_missing(c(1,5,7)) # 输出3，正确

补充说明 #

这个方案仅适用于缺失且仅缺失一个非首尾项的场景，刚好匹配你的需求。如果以后需要处理多个缺失项的情况，我们可以再调整，但针对当前的问题，这是最优的效率解决方案。

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