C++单循环高效查找二维数组重复行索引的方法

需求说明 #

查找二维数组中重复行对应的索引，行重复判定规则：若两行的第2个元素、第4个元素分别相等，则认定两行重复。

原有实现的问题 #

常规思路是双层嵌套循环逐行比对，示例代码如下：

std::unordered_set<int> result;
for (int i = 0; i < rows_count; ++i)
{
    for (int j = i + 1; j < rows_count; ++j)
    {
        if (arr[i][2] == arr[j][2] && arr[i][4] == arr[j][4])
        {
            result.insert(j); // 注：原示例写push_back是错误用法，unordered_set没有该方法，插入元素需用insert
        }
    }
}

该实现时间复杂度为O(n²)，当二维数组行数rows_count量级很大时，运行效率极低。

单层循环优化方案 #

可以直接借助STL容器实现无嵌套循环的高效查找，核心思路是用存储结构记录已经遍历过的行的判定特征，避免逐行重复比对，时间复杂度可降到O(nlogn)甚至平均O(n)，大数据量下性能提升非常明显。

实现逻辑 #

• 构造行判定键：仅取每行参与重复判定的第2、第4个元素，组合成唯一键值
• 初始化映射结构：用来保存「判定键 -> 该键第一次出现的行索引」的对应关系
• 单层遍历所有行：
  • 计算当前行的判定键
  • 如果键已存在于映射结构中，说明当前行是重复行，将当前行索引加入结果集
  • 如果键不存在，将当前键和行索引存入映射结构，继续遍历

代码示例 #

以下是兼容C++11及以上版本、无需额外自定义哈希函数的稳妥实现：

#include <unordered_set>
#include <map>
#include <vector>
#include <utility>

std::unordered_set<int> getDuplicateRowIndices(const std::vector<std::vector<int>>& arr) {
    std::unordered_set<int> result;
    // 存储判定键和首次出现的行索引，map为红黑树实现，单次查找复杂度O(logn)
    std::map<std::pair<int, int>, int> firstOccurMap;
    const int rowsCount = arr.size();
    for (int i = 0; i < rowsCount; ++i) {
        // 下标取值和原示例逻辑完全对齐，判定下标为2、4的元素相等即行重复
        std::pair<int, int> checkKey = {arr[i][2], arr[i][4]};
        if (firstOccurMap.count(checkKey)) {
            result.insert(i);
        } else {
            firstOccurMap[checkKey] = i;
        }
    }
    return result;
}

如果追求极致性能，可以为std::unordered_map实现std::pair<int,int>类型的哈希函数，替换代码中的std::map，即可得到平均O(n)时间复杂度的实现，在百万级以上行数的场景下，性能比双层嵌套循环高数百到数千倍。

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