如何高效计算向量中截至每个位置的不同元素数量？

核心思路 #

避开O(n²)复杂度的循环检查，转而标记每个元素的首次出现位置，再通过cumsum()累计首次出现的次数，就能得到每个位置的累计不同元素数。这种方法的时间复杂度为O(n)或O(n log n)，完全适配百万级规模的数据。

解法1：Base R 极简实现 #

利用match()快速定位每个元素的首次出现索引，再通过逻辑比较标记首次出现的位置，最后累计求和：

vec <- c("a", "b", "c", "a", "a", "c", "d", "a")

# 获取每个元素首次出现的索引
first_occur_idx <- match(vec, vec)
# 标记当前位置是否为该元素的首次出现，再累计求和
res <- cumsum(seq_along(vec) == first_occur_idx)
res
# [1] 1 2 3 3 3 3 4 4

原理：match(x, x)会返回每个元素在向量中第一次出现的位置，当当前索引等于首次出现索引时，说明这是该元素第一次出现，标记为TRUE（等价于1），cumsum()自动累计这些1的数量，得到累计不同元素数。

解法2：Data.table 大数据优化 #

如果向量规模极大（千万级以上），data.table的分组操作在内存效率和速度上更有优势：

library(data.table)

vec <- c("a", "b", "c", "a", "a", "c", "d", "a")
dt <- data.table(vec = vec, idx = seq_along(vec))

# 按元素分组，标记每组的第一个元素（即首次出现）
dt[, is_first := seq_len(.N) == 1, by = vec]
# 全局累计首次出现的次数
dt[, res := cumsum(is_first)]

dt$res
# [1] 1 2 3 3 3 3 4 4

解法3：Dplyr tidyverse 风格实现 #

若习惯使用tidyverse生态，可用dplyr的分组标记+累计求和：

library(dplyr)

vec <- c("a", "b", "c", "a", "a", "c", "d", "a")

tibble(vec = vec) %>%
  group_by(vec) %>%
  mutate(is_first = row_number() == 1) %>%
  ungroup() %>%
  mutate(res = cumsum(is_first)) %>%
  pull(res)
# [1] 1 2 3 3 3 3 4 4

为什么原方法慢？ #

原for循环中，每次vec[i] %in% vec[1:(i-1)]都要遍历前i-1个元素做检查，时间复杂度为O(n²)。当n达到百万时，计算量会指数级增长，导致耗时极长。而上面的方法都通过向量化或高效分组操作，将时间复杂度降到了线性或线性对数级别，大幅提升效率。

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