R语言：移除序列中不符合规则的元素，求更高效解法

你的需求是过滤序列s，仅保留满足每个后续元素要么等于前一个元素，要么比前一个元素大1的元素。原代码通过循环逐个删除不符合条件的元素，但频繁修改向量会导致内存反复分配，效率较低（时间复杂度O(n²)），以下是两种更高效的O(n)时间复杂度方案：

方案一：使用Reduce向量化处理 #

利用Reduce累积维护上一个合法元素的值，同时生成每个位置的合法预期值，最后筛选出匹配的元素：

s <- c(1,1,1,1,2,2,2,-2,3,3,4,8,8,8,9,5,5,12,6)

# 累积计算每个位置的合法预期值
valid <- Reduce(function(last, x) {
  if (x == last || x == last + 1) x else last
}, s, accumulate = TRUE)

# 筛选出符合预期的元素
result <- s[s == valid]

方案二：标记保留位置的循环优化 #

避免频繁修改向量，先标记所有需要保留的位置，最后一次性筛选：

s <- c(1,1,1,1,2,2,2,-2,3,3,4,8,8,8,9,5,5,12,6)

keep <- logical(length(s))
keep[1] <- TRUE  # 第一个元素默认保留
last_valid <- s[1]

for (i in 2:length(s)) {
  if (s[i] == last_valid || s[i] == last_valid + 1) {
    keep[i] <- TRUE
    last_valid <- s[i]
  }
}

result <- s[keep]

结果验证 #

两种方案最终得到的结果均为：

> result
 [1] 1 1 1 1 2 2 2 3 3 4 5 5 6

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