如何高效获取数值矩阵字典序最大的行（无需全排序）

当然可以避免全排序，通过逐列迭代筛选的方式就能高效定位到字典序最大的行，这种方法的时间复杂度比全排序更低，尤其适合处理大型矩阵。

核心思路是按列优先级依次筛选：

• 先找出第一列数值最大的所有行
• 在这些候选行里，再找出第二列数值最大的行
• 重复这个过程，直到候选行只剩1个或者遍历完所有列

下面是具体的R函数实现：

max_lex_row <- function(M) {
  rows <- seq_len(nrow(M))
  for (col in seq_len(ncol(M))) {
    # 获取当前候选行中该列的最大值
    col_max <- max(M[rows, col])
    # 筛选出该列等于最大值的候选行
    rows <- rows[M[rows, col] == col_max]
    # 如果只剩一行，提前结束循环
    if (length(rows) == 1) break
  }
  M[rows, , drop = FALSE]
}

测试验证 #

我们用一个示例矩阵来验证结果和全排序的一致性：

# 构造测试矩阵
set.seed(123)
M <- matrix(sample(1:5, 15, replace = TRUE), ncol = 3)

# 原方法得到的字典序最大行
original_max <- lexsort(M)[nrow(M), , drop = FALSE]

# 新方法得到的结果
new_max <- max_lex_row(M)

# 验证是否一致
all.equal(original_max, new_max)

运行后会返回TRUE，说明两种方法结果一致，但新方法不需要对整个矩阵排序，在数据量较大时性能提升明显。

内容的提问来源于stack exchange，提问作者Stéphane Laurent